秦 娜， 劉宴濤

（1.嘉應(yīng)學(xué)院 計(jì)算機(jī)學(xué)院，廣東 梅州 514015； 2.蒙古研究大學(xué)，蒙古 烏蘭巴托，14200）

無線傳感器網(wǎng)絡(luò)（簡(jiǎn)稱傳感網(wǎng)）是由一定數(shù)量的傳感器節(jié)點(diǎn)組成的無線多跳網(wǎng)絡(luò)，節(jié)點(diǎn)同時(shí)充當(dāng)終端和路由器，具有無中心、自組織、多跳路由、快速布設(shè)、不依賴基礎(chǔ)設(shè)施、體積小、能耗低、分布式、合作通信等特點(diǎn)。由于節(jié)點(diǎn)數(shù)目多，網(wǎng)絡(luò)規(guī)模大，因此路由變得非常復(fù)雜。另外，由于傳感器節(jié)點(diǎn)的故障、缺電或損毀等原因，會(huì)發(fā)生節(jié)點(diǎn)脫網(wǎng)現(xiàn)象，所以傳感網(wǎng)需要具有自愈合、自修復(fù)功能。

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

1 小世界網(wǎng)絡(luò)的基本概念

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

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

圖G中，假設(shè)節(jié)點(diǎn)i的度d（i）=ki，即有ki個(gè)節(jié)點(diǎn)與節(jié)點(diǎn)i相連，這ki個(gè)節(jié)點(diǎn)之間最多可能存在條邊，假設(shè)這ki個(gè)節(jié)點(diǎn)之間實(shí)際存在Ei條邊，則節(jié)點(diǎn)i的CC定義為

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

2 小世界網(wǎng)絡(luò)的理論分析

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

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

表1 小世界網(wǎng)絡(luò)的參數(shù)Tab. 1 Parameters of small world network

圖1 小世界柵格網(wǎng)絡(luò)Fig.1 Small world grid network

圖2 APL與強(qiáng)節(jié)點(diǎn)數(shù)目的關(guān)系Fig.2 The relationship between APL and number of strong nodes

圖3 CC與強(qiáng)節(jié)點(diǎn)數(shù)目的關(guān)系Fig.3 The relationship between CC and number of strong nodes

圖1 是基于UCINET 建立的傳感網(wǎng)理論模型，僅僅通過節(jié)點(diǎn)的相鄰關(guān)系統(tǒng)計(jì)APL 和CC，并沒有通信功能，下面將基于OPNET網(wǎng)絡(luò)仿真軟件構(gòu)建森林火險(xiǎn)監(jiān)防傳感網(wǎng)仿真模型，實(shí)現(xiàn)網(wǎng)絡(luò)的路由和傳輸功能，通過網(wǎng)絡(luò)仿真實(shí)驗(yàn)驗(yàn)證所提出的異構(gòu)網(wǎng)絡(luò)具有小世界特征。

3 小世界森林火險(xiǎn)監(jiān)防傳感網(wǎng)仿真系統(tǒng)

泛洪是無線多跳網(wǎng)絡(luò)必不可少的信息發(fā)布機(jī)制，既可以作為獨(dú)立的路由算法使用，又可以輔助動(dòng)態(tài)源路由協(xié)議、共享樹多播協(xié)議創(chuàng)建路由。泛洪可以建立滲流理論中的位置滲流模型，Bhaskar 等［9］研究了無線自組網(wǎng)滲流過程中的相變現(xiàn)象，Yoav等［10］研究了無線自組網(wǎng)的概率泛洪技術(shù)。這2 項(xiàng)研究發(fā)現(xiàn)了無線自組網(wǎng)存在相變現(xiàn)象，即當(dāng)泛洪概率p超過某個(gè)門限pc時(shí)，再增加泛洪概率p對(duì)網(wǎng)絡(luò)性能的提升貢獻(xiàn)不大。

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

同構(gòu)網(wǎng)絡(luò)和異構(gòu)網(wǎng)絡(luò)分別如圖4-5 所示，2 種網(wǎng)絡(luò)具有相同的網(wǎng)絡(luò)拓?fù)?。在圖4 的同構(gòu)傳感網(wǎng)中，所有節(jié)點(diǎn)都配備了一對(duì)收發(fā)信機(jī)，使用相同的頻段，具有相同的傳輸半徑，使用相同的泛洪概率。在圖5 的異構(gòu)傳感網(wǎng)中，為每個(gè)節(jié)點(diǎn)配備了1 個(gè)發(fā)射機(jī)和2 個(gè)接收機(jī)，全網(wǎng)使用2 個(gè)發(fā)射頻段，1 個(gè)用于強(qiáng)節(jié)點(diǎn)，1 個(gè)用于普通節(jié)點(diǎn)。所有節(jié)點(diǎn)都能接收這2 個(gè)頻段的信號(hào)。強(qiáng)節(jié)點(diǎn)的通信半徑是普通節(jié)點(diǎn)的2 倍。另外，強(qiáng)節(jié)點(diǎn)使用比普通節(jié)點(diǎn)高的泛洪概率，因此稱之為非均勻概率泛洪算法。

圖4 同構(gòu)網(wǎng)絡(luò)的概率泛洪Fig.4 Probability flooding of homogeneous network

圖5 異構(gòu)網(wǎng)絡(luò)的概率泛洪Fig.5 Probability flooding of heterogeneous network

由圖4-5 可見，在2 000 m×2 000 m 的矩形范圍內(nèi)隨機(jī)分布著400 個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)中只有1 個(gè)源節(jié)點(diǎn)，其坐標(biāo)位于網(wǎng)絡(luò)中心位置，即（1 000， 1 000），源節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)包并向網(wǎng)絡(luò)泛洪。其他節(jié)點(diǎn)均為宿節(jié)點(diǎn)，不產(chǎn)生數(shù)據(jù)包，只接收數(shù)據(jù)包。網(wǎng)絡(luò)層采用概率泛洪技術(shù)，媒體存取層采用802.11分布式協(xié)調(diào)功能協(xié)議。

仿真過程中，隨著泛洪概率p從0向1遞增，收集2個(gè)結(jié)果參數(shù)：（1） 收到數(shù)據(jù)包的節(jié)點(diǎn)數(shù)目，該參數(shù)反映了概率泛洪的有效覆蓋范圍；（2） 從源節(jié)點(diǎn)到宿節(jié)點(diǎn)的平均跳數(shù)，該參數(shù)可以對(duì)應(yīng)于網(wǎng)絡(luò)的APL。

Yang 等［11］研究發(fā)現(xiàn)，無線多跳網(wǎng)絡(luò)的聯(lián)通性與節(jié)點(diǎn)的平均度相關(guān)，后者由式（3）給出。

其中k表示節(jié)點(diǎn)的平均度，S表示網(wǎng)絡(luò)覆蓋范圍，R表示節(jié)點(diǎn)通信半徑，m表示節(jié)點(diǎn)數(shù)目。文獻(xiàn)［11］研究發(fā)現(xiàn)，當(dāng)節(jié)點(diǎn)度為6 時(shí)，網(wǎng)絡(luò)覆蓋范圍可達(dá)95%。就圖4-5 的仿真網(wǎng)絡(luò)而言，如果通信半徑設(shè)定為100 m，由式（3）可得節(jié)點(diǎn)平均度僅為2.14，網(wǎng)絡(luò)聯(lián)通性太差。為了提高網(wǎng)絡(luò)聯(lián)通性，降低網(wǎng)絡(luò)斷裂給泛洪帶來的影響，仿真實(shí)驗(yàn)將同構(gòu)網(wǎng)絡(luò)的節(jié)點(diǎn)通信半徑設(shè)定為200 m，異構(gòu)網(wǎng)絡(luò)中普通節(jié)點(diǎn)的通信半徑設(shè)定為150 m，強(qiáng)節(jié)點(diǎn)的通信半徑設(shè)定為300 m。

圖6-7 分別給出了收到數(shù)據(jù)包的節(jié)點(diǎn)數(shù)目和平均跳數(shù)隨著泛洪概率p的變化關(guān)系，實(shí)驗(yàn)結(jié)果證明異構(gòu)網(wǎng)絡(luò)以更小的通信半徑卻達(dá)到了比同構(gòu)網(wǎng)絡(luò)更好的性能，具體表現(xiàn)在以下3個(gè)方面。

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

（1）覆蓋范圍增益：圖6 中收到數(shù)據(jù)包的節(jié)點(diǎn)數(shù)目反映了泛洪的有效覆蓋范圍，可見小世界異構(gòu)網(wǎng)絡(luò)使用p=0.2 的泛洪概率就達(dá)到了同構(gòu)網(wǎng)絡(luò)使用p=0.6 的泛洪概率的覆蓋范圍，約390 個(gè)節(jié)點(diǎn)收到了數(shù)據(jù)包。就傳感網(wǎng)而言，更小的泛洪概率意味著更小的全網(wǎng)功率消耗和更少的信號(hào)沖突，提高了網(wǎng)絡(luò)的健壯性，延長(zhǎng)了網(wǎng)絡(luò)的工作時(shí)間。

（2）功率消耗增益：在仿真設(shè)置中，同構(gòu)網(wǎng)絡(luò)全部400 個(gè)節(jié)點(diǎn)的通信半徑設(shè)為200 m，異構(gòu)網(wǎng)絡(luò)20%（80個(gè)節(jié)點(diǎn)）的強(qiáng)節(jié)點(diǎn)的通信半徑設(shè)為300 m，80%（320 個(gè)節(jié)點(diǎn)）普通節(jié)點(diǎn)的通信半徑設(shè)為150 m。根據(jù)自由空間傳輸公式（4）可以計(jì)算，為了獲得相同的接收功率Pr，小世界異構(gòu)網(wǎng)絡(luò)可以使用比同構(gòu)網(wǎng)絡(luò)少13.57%的發(fā)射功率Pt。

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

（3）平均跳數(shù)增益：圖7 顯示小世界異構(gòu)網(wǎng)絡(luò)的平均跳數(shù)明顯少于同構(gòu)網(wǎng)絡(luò)。更少的平均跳數(shù)意味著更少的處理和傳輸延時(shí)，這對(duì)于火情預(yù)警等實(shí)時(shí)應(yīng)用是至關(guān)重要的。需要說明的是圖7 中當(dāng)泛洪概率低于0.3 時(shí)，同構(gòu)網(wǎng)絡(luò)的平均跳數(shù)少于異構(gòu)網(wǎng)絡(luò)，但對(duì)應(yīng)圖6 可以發(fā)現(xiàn)此時(shí)同構(gòu)網(wǎng)絡(luò)的覆蓋范圍是很小的，只有不到100 個(gè)節(jié)點(diǎn)收到了數(shù)據(jù)包，所以此時(shí)的平均跳數(shù)不能反映網(wǎng)絡(luò)的有效性能。

圖7 平均跳數(shù)Fig. 7 Average hop number

4 結(jié) 論

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