基于小世界特征的無線傳感器網(wǎng)絡(luò)拓?fù)鋬?yōu)化

羅小娟　黃如

摘 要：針對無線傳感器網(wǎng)絡(luò)存在的能量消耗問題，在基于復(fù)雜網(wǎng)絡(luò)小世界特征基礎(chǔ)上，通過在無線傳感器網(wǎng)絡(luò)中增加超級節(jié)點(diǎn)，并在超級節(jié)點(diǎn)之間建立超級鏈路，提出一種具有小世界特征效應(yīng)的無線網(wǎng)絡(luò)模型。從復(fù)雜網(wǎng)絡(luò)的視角計(jì)算分析了在傳感器網(wǎng)絡(luò)中部署超級節(jié)點(diǎn)對網(wǎng)絡(luò)節(jié)點(diǎn)能量效率的影響。仿真研究結(jié)果顯示，在傳感器網(wǎng)絡(luò)中適當(dāng)增設(shè)少量超級節(jié)點(diǎn)，可大幅減少網(wǎng)絡(luò)的平均路徑長度，明顯改善網(wǎng)絡(luò)傳輸性能，同時(shí)極大地提高了網(wǎng)絡(luò)節(jié)點(diǎn)的節(jié)能比率。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；復(fù)雜網(wǎng)絡(luò)；拓?fù)鋬?yōu)化；小世界特征

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2018）03-00-03

0 引 言

經(jīng)典的復(fù)雜網(wǎng)絡(luò)理論已經(jīng)證明： “小世界效應(yīng)”在社會關(guān)系網(wǎng)絡(luò)中廣泛存在[1，2]。小世界現(xiàn)象的本質(zhì)特征是具有小的平均路徑長度和大的集聚系數(shù)[3，4]。小世界特征普遍存在于如計(jì)算機(jī)互聯(lián)網(wǎng)、科學(xué)家合作網(wǎng)、社會關(guān)系網(wǎng)等現(xiàn)實(shí)網(wǎng)絡(luò)中，同時(shí)小世界理論還廣泛存在于電力網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)等系統(tǒng)中[5，6]。真實(shí)的網(wǎng)絡(luò)可以分為關(guān)系網(wǎng)絡(luò)與空間網(wǎng)絡(luò)兩大類。在關(guān)系網(wǎng)絡(luò)（Relation Network）的拓?fù)浣Y(jié)構(gòu)中，節(jié)點(diǎn)之間的連接與節(jié)點(diǎn)距離和位置無關(guān)，節(jié)點(diǎn)之間的距離以跳數(shù)來計(jì)算；空間網(wǎng)絡(luò)（Spatial Network）節(jié)點(diǎn)之間的連接與節(jié)點(diǎn)之間的距離和位置緊密相關(guān)。傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)研究通常都將社會關(guān)系或者技術(shù)網(wǎng)絡(luò)抽象為關(guān)系網(wǎng)絡(luò)，屬于關(guān)系圖的范疇；無線Ad-Hoc網(wǎng)絡(luò)與無線傳感器網(wǎng)絡(luò)由于其傳輸半徑的限制，是空間網(wǎng)絡(luò)，屬于空間圖的范疇。空間網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與連通性及傳輸半徑緊密相關(guān)。

小世界特征是指網(wǎng)絡(luò)較小的平均路徑長度和大的聚類系數(shù)，無線傳感網(wǎng)絡(luò)中節(jié)點(diǎn)之間采用無線多跳方式傳輸數(shù)據(jù)，引入小世界特征可以降低網(wǎng)絡(luò)系統(tǒng)的通信開銷，并增強(qiáng)網(wǎng)絡(luò)的容錯性，從而延長整個系統(tǒng)的生存時(shí)間[7-11]。張[12]等選擇性地刪除一些邊，基于匯聚節(jié)點(diǎn)建立捷徑，交替進(jìn)行，直到兩個小世界特征達(dá)到最優(yōu)。周[13]等基于小世界與能效提出了一種容遲網(wǎng)絡(luò)路由算法。Nardis[14]等設(shè)計(jì)了一種自適應(yīng)選舉簇頭，簇頭之間動態(tài)建立捷徑，生成具有小世界特征的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，實(shí)驗(yàn)結(jié)果顯示了該網(wǎng)絡(luò)的優(yōu)良性能。

根據(jù)傳感網(wǎng)應(yīng)用環(huán)境的不同，部署方式可以分為確定性部署和隨機(jī)部署兩類。在監(jiān)測范圍小且人類方便到達(dá)的應(yīng)用環(huán)境如車間、醫(yī)院、商場中，可以預(yù)先確定傳感器節(jié)點(diǎn)的位置并手工部署在確定位置上。但當(dāng)網(wǎng)絡(luò)規(guī)模較大或在環(huán)境惡劣危險(xiǎn)的場合應(yīng)用時(shí)，如湖泊、沼澤、沙漠、戰(zhàn)場、疫區(qū)等，通常采用隨機(jī)播撒方式。本文在無線傳感網(wǎng)中引入復(fù)雜網(wǎng)絡(luò)中的小世界特征，結(jié)合確定性部署和隨機(jī)部署方式，在隨機(jī)部署的基礎(chǔ)上，確定部署少量具有更高能量、更強(qiáng)數(shù)據(jù)處理能力的超級節(jié)點(diǎn)，在超級節(jié)點(diǎn)和匯聚節(jié)點(diǎn)之間建立超級鏈路形成直接通信的可靠捷徑，從而構(gòu)建基于無線傳感器網(wǎng)絡(luò)小世界效應(yīng)的網(wǎng)絡(luò)模型。

1 小世界效應(yīng)的傳感器網(wǎng)絡(luò)模型

1.1 網(wǎng)絡(luò)模型設(shè)計(jì)

在無線傳感網(wǎng)絡(luò)應(yīng)用中，通常傳感器節(jié)點(diǎn)一旦部署，位置便相對固定，且需長期運(yùn)行監(jiān)測如森林火災(zāi)檢測的應(yīng)用場景，本文采用的網(wǎng)絡(luò)模型為N個傳感器節(jié)點(diǎn)均勻部署在一個X×Y的長方形區(qū)域Z內(nèi)，每個節(jié)點(diǎn)均勻分布在交叉點(diǎn)上，為了避免網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)經(jīng)常改變，假定所有傳感器節(jié)點(diǎn)一旦部署位置固定，且這些節(jié)點(diǎn)是同構(gòu)的，具有相同的能量和相同的通信半徑，并知道自己的位置信息，位置采用平面坐標(biāo)（x，y）標(biāo)記，其中0≤x≤X-1，0≤y≤Y-1。網(wǎng)絡(luò)拓?fù)湫纬善矫鍹esh結(jié)構(gòu)，如圖1所示。

傳感器節(jié)點(diǎn)只與臨近節(jié)點(diǎn)即與自己垂直和水平方向的節(jié)點(diǎn)傳送和接收數(shù)據(jù)，匯聚節(jié)點(diǎn)可以部署于區(qū)域范圍內(nèi)的任何位置，傳感器節(jié)點(diǎn)以一定的速率發(fā)送數(shù)據(jù)傳到匯聚節(jié)點(diǎn)，匯聚節(jié)點(diǎn)可以與其他有線網(wǎng)絡(luò)或者無線網(wǎng)絡(luò)連接，最后傳送到用戶終端。傳感器節(jié)點(diǎn)也可采用貪婪路由策略，即數(shù)據(jù)經(jīng)最短距離傳送到匯聚節(jié)點(diǎn)。

1.2 小世界效應(yīng)分析

假設(shè)已知普通節(jié)點(diǎn)Ni的平面坐標(biāo)位置為（xi，yi），普通節(jié)點(diǎn)Nj位于（xj，yj），匯聚節(jié)點(diǎn)Sink的平面坐標(biāo)位置為（xs，ys）。先計(jì)算普通節(jié)點(diǎn)Ni和Nj不經(jīng)過超級節(jié)點(diǎn)把數(shù)據(jù)發(fā)送給匯聚節(jié)點(diǎn)的最短跳數(shù)距離為：

如圖1所示，如果普通節(jié)點(diǎn)Ni遠(yuǎn)離匯聚節(jié)點(diǎn)，Ni先以無線多跳的方式將數(shù)據(jù)發(fā)送給最近的超級節(jié)點(diǎn)，超級節(jié)點(diǎn)通過超級鏈路直接傳送給匯聚節(jié)點(diǎn)。此時(shí)，Ni節(jié)點(diǎn)把數(shù)據(jù)發(fā)送給最近超級節(jié)點(diǎn)的最短跳數(shù)為：

當(dāng)H（Ni， S）≥H' （Ni， S）時(shí)，節(jié)點(diǎn)選擇經(jīng)超級節(jié)點(diǎn)發(fā)送數(shù)據(jù)。反之，當(dāng)H（Nj，S）

小世界網(wǎng)絡(luò)具有較小的特征路徑長度。在一般復(fù)雜網(wǎng)絡(luò)中，特征路徑長度指網(wǎng)絡(luò)中任意兩點(diǎn)之間最短路徑的平均值。在無線傳感網(wǎng)絡(luò)中，所有傳感器節(jié)點(diǎn)感知的數(shù)據(jù)均向匯聚節(jié)點(diǎn)匯集，傳送數(shù)據(jù)具有明確的方向性，數(shù)據(jù)流向是一種“多對一”的集中匯聚模式，在本節(jié)仿真分析中給匯聚節(jié)點(diǎn)設(shè)定了特定的地理位置，所以平均路徑長度需要根據(jù)傳感器網(wǎng)絡(luò)的特殊性進(jìn)行修正。這里的平均路徑長度APL指為傳感網(wǎng)絡(luò)中所有節(jié)點(diǎn)發(fā)送數(shù)據(jù)到達(dá)匯聚節(jié)點(diǎn)所經(jīng)過的通信跳數(shù)平均值，表示為：

其中：n為網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的個數(shù)；Hi-sink表示節(jié)點(diǎn)i到超級節(jié)點(diǎn)或匯聚節(jié)點(diǎn)的通信跳數(shù)距離，即為傳感器網(wǎng)絡(luò)中普通節(jié)點(diǎn)i到匯聚節(jié)點(diǎn)通信的所有路徑中最短傳輸路徑的跳數(shù)，表示為：

假設(shè)在同構(gòu)網(wǎng)絡(luò)中加入μ個超級節(jié)點(diǎn)后，普通節(jié)點(diǎn)通過超級節(jié)點(diǎn)傳送數(shù)據(jù)的概率為ρi，μ，在一個大規(guī)模的無線傳感器網(wǎng)絡(luò)應(yīng)用中，ρi，μ隨著μ值的增加而增大，則網(wǎng)絡(luò)節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的路徑長度平均約為：

在初始的同構(gòu)網(wǎng)絡(luò)中，沒有增設(shè)超級節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的平均路徑長度為：

所以，在同構(gòu)Mesh網(wǎng)絡(luò)與通過增設(shè)μ個超級節(jié)點(diǎn)而構(gòu)造生成的超級鏈路網(wǎng)絡(luò)之間，網(wǎng)絡(luò)節(jié)點(diǎn)到超級節(jié)點(diǎn)或匯聚節(jié)點(diǎn)的平均路徑長度的比率定義為平均路徑長度的變化率，記為：

在傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的能量消耗主要用于數(shù)據(jù)處理與傳輸，所以網(wǎng)絡(luò)能耗與數(shù)據(jù)傳輸?shù)钠骄窂介L度密切相關(guān)，定義能量節(jié)省比率為：

能量節(jié)省比率越大，表示傳感器網(wǎng)絡(luò)的能量效率越高。

對于增設(shè)了超級節(jié)點(diǎn)后的無線傳感器網(wǎng)絡(luò)，超級節(jié)點(diǎn)周圍的普通節(jié)點(diǎn)通過超級節(jié)點(diǎn)發(fā)送數(shù)據(jù)，網(wǎng)絡(luò)拓?fù)浒l(fā)生相應(yīng)變化，網(wǎng)絡(luò)出現(xiàn)聚類特性，可認(rèn)為具有較高的聚類系數(shù)。

1.3 仿真結(jié)果

仿真實(shí)驗(yàn)采用規(guī)模為20×20的Mesh網(wǎng)絡(luò)，普通節(jié)點(diǎn)部署在Mesh網(wǎng)絡(luò)中的交叉點(diǎn)上，匯聚節(jié)點(diǎn)分別部署在（0，0）和網(wǎng)絡(luò)的中心（10，10）位置，假設(shè)超級節(jié)點(diǎn)同樣均勻部署在監(jiān)測環(huán)境中，如圖2所示。

平均路徑長度（APL）與超級節(jié)點(diǎn)的關(guān)系如圖3所示，展示了網(wǎng)絡(luò)中超級節(jié)點(diǎn)數(shù)和平均路徑長度APL（μ）之間的關(guān)系。圖中顯示了添加網(wǎng)絡(luò)中的部分超級節(jié)點(diǎn)，超級節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)的平均路徑長度迅速下降，尤其在匯聚節(jié)點(diǎn)處（0，0）比（10，10）提高更為顯著，當(dāng)匯聚節(jié)點(diǎn)處在（0，0）的位置時(shí)，超級節(jié)點(diǎn)增加1～6個，平均路徑長度由10降至4。然而，當(dāng)超級節(jié)點(diǎn)繼續(xù)增加時(shí)，平均路徑長度下降非常緩慢。結(jié)果表明，在同構(gòu)網(wǎng)絡(luò)中加入少量超級節(jié)點(diǎn)，平均路徑長度迅速下降，網(wǎng)絡(luò)具有小世界特征。

平均路徑長度變化率APLR（μ）與超級節(jié)點(diǎn)數(shù)的關(guān)系如圖4所示。在兩個模擬環(huán)境中都添加了6個超級節(jié)點(diǎn)，網(wǎng)絡(luò)的平均路徑長度減少約至45%。由曲線可知，若繼續(xù)增加超級節(jié)點(diǎn)的數(shù)量，路徑長度將不再顯著減少。因此，合理增加超級節(jié)點(diǎn)對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)沒有太大影響，但可以大大減少數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)路徑長度，進(jìn)一步體現(xiàn)了小世界復(fù)雜網(wǎng)絡(luò)的特點(diǎn)。

網(wǎng)絡(luò)節(jié)能比率與增設(shè)超級節(jié)點(diǎn)的關(guān)系如圖5所示。當(dāng)增加第1～6條超級鏈路時(shí)，網(wǎng)絡(luò)節(jié)能比率約50%，但增加更多超級鏈路后節(jié)能效果不明顯。且當(dāng)匯聚節(jié)點(diǎn)位于（0，0）時(shí)，比位于（10，10） 時(shí)節(jié)能效果有明顯提高。

2 結(jié) 語

本文首先分析了小世界效應(yīng)在無線傳感器網(wǎng)絡(luò)中的應(yīng)用和研究。在無線傳感網(wǎng)絡(luò)中，引入超級節(jié)點(diǎn)和超級鏈路，提出了小世界特征的網(wǎng)絡(luò)模型，仿真分析了超級節(jié)點(diǎn)數(shù)對網(wǎng)絡(luò)平均路徑長度、路徑長度變化率和網(wǎng)絡(luò)節(jié)能率的影響，增加少量超級節(jié)點(diǎn)可以減少網(wǎng)絡(luò)數(shù)據(jù)傳輸延遲，提高網(wǎng)絡(luò)的能量效率。本文考慮的是節(jié)點(diǎn)均勻分布在Mesh網(wǎng)絡(luò)的交叉點(diǎn)上，針對無線傳感器網(wǎng)絡(luò)隨機(jī)分布節(jié)點(diǎn)的情況，增設(shè)超級節(jié)點(diǎn)的節(jié)能問題還須進(jìn)一步討論。

參考文獻(xiàn)

[1] MILGRAM S. The small world problem. Psychology Today[Z]. 1967： 60-67.

[2] KLEINBERG J. Navigation in a small world[J].Nature， 2000： 845-845.

[3] WATTS D J， STROGATZ S H. Collective dynamics of ‘small-world networks[J].Nature，1998： 440-442.

[4] NEWMAN M E J，WATTS D J. Renormalization group analysis of the small-world network mode[J].Physics Letters A，1999， 263（3-4）： 341-346.

[5] Ye X，Xu L，Lin L. Small-word model based topology optimization in wireless Sensor networks[C].Proceeding of the IEEE international conference on information science and engineering，2008.

[6] HUI K Y K， LUI J C S， YAU D K Y. Small-world overlay P2P networks：construction， management and handling of dynamic flash crowds[J].Computer networks，2006， 50（15）： 2727-2746 .

[7] ZHENG P， TANG W， ZHANG J. A simple method for designing efficient small-world neural networks[J].Neural networks，2010， 23（2）： 155-159.

[8] HELMY A. Small worlds in wireless networks[J].IEEE communications letters， 2003， 7（10）：490 -492.

[9] SHARMA G，MAZUMDAR R. A case for hybrid sensor networks[J].IEEE/ACM transactions on network，2008，16（5）： 1121-1132.

[10] GUIDONI D L， MINI R A，LOUREIRO A A. On the design of resilient heterogeneous wireless sensor networks based on small world concepts[J]. Computer networks，2010， 54（8）： 1266-1281.

[11] KOMURO N，MOTEGI S，SANADA K，et al. Small-World-Network model based routing method for wireless sensor networks[J].IEICE transactions of commununications，2016（11） ： 2315-2322.

[12]張靜蓮，劉三陽，張朝輝.具有小世界現(xiàn)象的無線傳感器網(wǎng)絡(luò)構(gòu)造方法[J].信號處理，2017，33（3）：417-421.

[13]周朝榮，徐小瓊，楊柳，等.基于小世界與能效的容遲網(wǎng)絡(luò)路由算法[J].電子科技大學(xué)學(xué)報(bào)，2016，45（1）：129-134.

[14]熊書明，胡永娣.基于小世界概念的異構(gòu)傳感器網(wǎng)絡(luò)拓?fù)淇刂芠J].計(jì)算機(jī)工程與設(shè)計(jì)，2016，37（11）：2869-2875.