小世界森林火險監防傳感網

秦 娜， 劉宴濤

（1.嘉應學院 計算機學院，廣東 梅州 514015； 2.蒙古研究大學，蒙古 烏蘭巴托，14200）

無線傳感器網絡（簡稱傳感網）是由一定數量的傳感器節點組成的無線多跳網絡，節點同時充當終端和路由器，具有無中心、自組織、多跳路由、快速布設、不依賴基礎設施、體積小、能耗低、分布式、合作通信等特點。由于節點數目多，網絡規模大，因此路由變得非常復雜。另外，由于傳感器節點的故障、缺電或損毀等原因，會發生節點脫網現象，所以傳感網需要具有自愈合、自修復功能。

傳感網可用于工業控制［1］、生態監測［2］、智能交通［3］等應用領域，還可以用于森林火險監防預警。山區林地由于面積遼闊，人員稀少，單純依靠人工監測不易及早地發現火險隱患。大量溫度、濕度和煙霧傳感器可以通過無人機或者人工播撒在監防區域，這些傳感器的節點具有智能計算和無線通信功能，可以自行組網，自行通信，在無人值守的狀態下以多跳的方式將火警信息快速傳遞給指揮中心，能及早感知火險，而且智能化火警信息能準確報告火點、火情、火勢、溫度、濕度，甚至風向等，提高預警準確度。但是傳統的傳感網屬于同構網絡，節點具有相同的通信范圍，而且森林火險監防范圍大，網絡跳數多，消息延時，不利于火情信息的實時傳輸和快速反應。為此，本研究基于小世界網絡思想，應用概率泛洪方法，建立小世界森林火險監防傳感網仿真系統，通過理論分析和仿真實驗證明該系統的性能。

1 小世界網絡的基本概念

小世界網絡屬于復雜網絡的范疇，1967 年Milgram 通過信件傳遞實驗研究了在社交網絡中路徑長度分布問題，提出了六度分離理論［4］。Newman等［5］發現對規則圖重連或增加少量隨機連接可以降低圖的平均路徑長度（Average path length，APL）和提高圖的集聚系數（Clustering coefficient，CC）。這樣的圖被稱為小世界網絡［6-7］。

在圖論中，網絡被定義成點集V和邊集E組成的圖G=（V，E）。如果圖G中任意節點對（u，v）和（v，u）對應同一條邊，則稱該網絡為無向網絡，否則就稱為有向網絡。無向網絡中節點v的度表示與v相連的節點數目，記作d（v），所有節點度的平均值稱為該網絡的平均度。圖G中任意2 個節點i和j的距離lij定義為i和j之間最短路徑的邊數，假設圖G中有n個節點，網絡的APL 定義為網絡中全部個節點之間距離的平均值，即

圖G中，假設節點i的度d（i）=ki，即有ki個節點與節點i相連，這ki個節點之間最多可能存在條邊，假設這ki個節點之間實際存在Ei條邊，則節點i的CC定義為

可見CC 描述了一個節點的相鄰節點之間相互連接、相互聚合的程度。網絡的CC 定義為所有節點CC的平均值。Ci=0 表示網絡中全部節點都是孤立節點，Ci=1 表示該網絡是全連通網絡，即網絡中任意2 個節點都存在邊連接［8］。

2 小世界網絡的理論分析

與Milgram 實驗研究的社交網絡不同，無線傳感網屬于空間圖的范疇，節點間是否存在鏈路并非隨機的，而是取決于節點間距離。傳統的無線傳感網是同構的，即網絡中所有無線節點具有相同的通信半徑R，節點只和緊鄰節點有邊相連，這種網絡由于缺少長程連接，所以不具備小世界特征。當用于傳輸森林火險監防預警信息時，由于網絡跳數多，延時長，不利于實時火情的快速預警。因此，需要借鑒小世界思想，對傳統的傳感網改造并賦予其小世界特征，縮短APL，降低消息延時。為此，可以在無線節點中選擇一部分“強節點”，擴大其通信半徑R，從而建立長程連接并構成異構網絡。

圖1 給出了一個基于UCINET 網絡分析軟件構建的柵格網絡，該網絡由400 個節點（20×20）排列而成，每個節點最多有4 個鄰居節點。從這400 個節點中隨機選擇n個節點作為強節點，其通信半徑是普通節點的2 倍（可以通過降低比特率或配備多套收發信機實現），因此強節點的鄰居節點可以多達12 個。改變節點數量n的值并基于UCINET 的統計功能可以得到APL 和CC 隨節點數量n變化的函數關系，如表1、圖2-3 所示。由圖2-3 可見，少量強節點的引入即可明顯地降低APL 和提升CC，當強節點達到網絡全部節點的20%（80 個）時，APL 和CC 已經接近各自的極值，從20%之后再繼續增加強節點的數目對APL和CC 增益的貢獻不大。這說明所構造的異構傳感網具有相變現象，僅僅選擇五分之一的節點充當強節點即可為傳感網賦予小世界特征，網絡性能獲得極大提升。

表1 小世界網絡的參數Tab. 1 Parameters of small world network

圖1 小世界柵格網絡Fig.1 Small world grid network

圖2 APL與強節點數目的關系Fig.2 The relationship between APL and number of strong nodes

圖3 CC與強節點數目的關系Fig.3 The relationship between CC and number of strong nodes

圖1 是基于UCINET 建立的傳感網理論模型，僅僅通過節點的相鄰關系統計APL 和CC，并沒有通信功能，下面將基于OPNET網絡仿真軟件構建森林火險監防傳感網仿真模型，實現網絡的路由和傳輸功能，通過網絡仿真實驗驗證所提出的異構網絡具有小世界特征。

3 小世界森林火險監防傳感網仿真系統

泛洪是無線多跳網絡必不可少的信息發布機制，既可以作為獨立的路由算法使用，又可以輔助動態源路由協議、共享樹多播協議創建路由。泛洪可以建立滲流理論中的位置滲流模型，Bhaskar 等［9］研究了無線自組網滲流過程中的相變現象，Yoav等［10］研究了無線自組網的概率泛洪技術。這2 項研究發現了無線自組網存在相變現象，即當泛洪概率p超過某個門限pc時，再增加泛洪概率p對網絡性能的提升貢獻不大。

借鑒上文提出的小世界異構網絡模型，提出一種非均勻概率泛洪算法，基于該算法把小世界異構傳感網和非小世界同構傳感網加以比較。

同構網絡和異構網絡分別如圖4-5 所示，2 種網絡具有相同的網絡拓撲。在圖4 的同構傳感網中，所有節點都配備了一對收發信機，使用相同的頻段，具有相同的傳輸半徑，使用相同的泛洪概率。在圖5 的異構傳感網中，為每個節點配備了1 個發射機和2 個接收機，全網使用2 個發射頻段，1 個用于強節點，1 個用于普通節點。所有節點都能接收這2 個頻段的信號。強節點的通信半徑是普通節點的2 倍。另外，強節點使用比普通節點高的泛洪概率，因此稱之為非均勻概率泛洪算法。

圖4 同構網絡的概率泛洪Fig.4 Probability flooding of homogeneous network

圖5 異構網絡的概率泛洪Fig.5 Probability flooding of heterogeneous network

由圖4-5 可見，在2 000 m×2 000 m 的矩形范圍內隨機分布著400 個節點，網絡中只有1 個源節點，其坐標位于網絡中心位置，即（1 000， 1 000），源節點產生數據包并向網絡泛洪。其他節點均為宿節點，不產生數據包，只接收數據包。網絡層采用概率泛洪技術，媒體存取層采用802.11分布式協調功能協議。

仿真過程中，隨著泛洪概率p從0向1遞增，收集2個結果參數：（1） 收到數據包的節點數目，該參數反映了概率泛洪的有效覆蓋范圍；（2） 從源節點到宿節點的平均跳數，該參數可以對應于網絡的APL。

Yang 等［11］研究發現，無線多跳網絡的聯通性與節點的平均度相關，后者由式（3）給出。

其中k表示節點的平均度，S表示網絡覆蓋范圍，R表示節點通信半徑，m表示節點數目。文獻［11］研究發現，當節點度為6 時，網絡覆蓋范圍可達95%。就圖4-5 的仿真網絡而言，如果通信半徑設定為100 m，由式（3）可得節點平均度僅為2.14，網絡聯通性太差。為了提高網絡聯通性，降低網絡斷裂給泛洪帶來的影響，仿真實驗將同構網絡的節點通信半徑設定為200 m，異構網絡中普通節點的通信半徑設定為150 m，強節點的通信半徑設定為300 m。

圖6-7 分別給出了收到數據包的節點數目和平均跳數隨著泛洪概率p的變化關系，實驗結果證明異構網絡以更小的通信半徑卻達到了比同構網絡更好的性能，具體表現在以下3個方面。

圖6 泛洪覆蓋范圍Fig. 6 Coverage of flooding

（1）覆蓋范圍增益：圖6 中收到數據包的節點數目反映了泛洪的有效覆蓋范圍，可見小世界異構網絡使用p=0.2 的泛洪概率就達到了同構網絡使用p=0.6 的泛洪概率的覆蓋范圍，約390 個節點收到了數據包。就傳感網而言，更小的泛洪概率意味著更小的全網功率消耗和更少的信號沖突，提高了網絡的健壯性，延長了網絡的工作時間。

（2）功率消耗增益：在仿真設置中，同構網絡全部400 個節點的通信半徑設為200 m，異構網絡20%（80個節點）的強節點的通信半徑設為300 m，80%（320 個節點）普通節點的通信半徑設為150 m。根據自由空間傳輸公式（4）可以計算，為了獲得相同的接收功率Pr，小世界異構網絡可以使用比同構網絡少13.57%的發射功率Pt。

其中，Pt表示發射功率，Pr表示接收功率，Gt表示發射天線增益，Gr表示接收天線增益，λ表示波長，d表示傳輸距離。

（3）平均跳數增益：圖7 顯示小世界異構網絡的平均跳數明顯少于同構網絡。更少的平均跳數意味著更少的處理和傳輸延時，這對于火情預警等實時應用是至關重要的。需要說明的是圖7 中當泛洪概率低于0.3 時，同構網絡的平均跳數少于異構網絡，但對應圖6 可以發現此時同構網絡的覆蓋范圍是很小的，只有不到100 個節點收到了數據包，所以此時的平均跳數不能反映網絡的有效性能。

圖7 平均跳數Fig. 7 Average hop number

4 結 論

傳感器網絡可以用于森林火險監防預警，相比人工監測，傳感網監測具有廣覆蓋、早感知、智能化、準確度高等特點。但是傳統的傳感器網絡屬于同構網絡，用于森林防火監測時具有跳數多、消息延時、實時性差等缺點。為此，借鑒小世界網絡思想，應用概率泛洪方法，通過在網絡中選取一部分強節點，擴大其通信半徑為普通節點的2 倍，構造小世界異構網絡?；赨CINET 的理論分析和基于OPNET 的仿真實驗證明改進的異構網絡具有相變現象，只需要選取20%的強節點即可建立小世界傳感網，明顯降低APL 和網絡功率消耗，增加覆蓋范圍，提高CC。改進的小世界森林火險監防傳感網可以縮短火警信息上報時間，提高反應速度。