基于小世界特征的無線傳感器網絡拓撲優化

羅小娟　黃如

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

關鍵詞：無線傳感器網絡；復雜網絡；拓撲優化；小世界特征

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2018）03-00-03

0 引 言

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

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

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

1 小世界效應的傳感器網絡模型

1.1 網絡模型設計

在無線傳感網絡應用中，通常傳感器節點一旦部署，位置便相對固定，且需長期運行監測如森林火災檢測的應用場景，本文采用的網絡模型為N個傳感器節點均勻部署在一個X×Y的長方形區域Z內，每個節點均勻分布在交叉點上，為了避免網絡拓撲結構經常改變，假定所有傳感器節點一旦部署位置固定，且這些節點是同構的，具有相同的能量和相同的通信半徑，并知道自己的位置信息，位置采用平面坐標（x，y）標記，其中0≤x≤X-1，0≤y≤Y-1。網絡拓撲形成平面Mesh結構，如圖1所示。

傳感器節點只與臨近節點即與自己垂直和水平方向的節點傳送和接收數據，匯聚節點可以部署于區域范圍內的任何位置，傳感器節點以一定的速率發送數據傳到匯聚節點，匯聚節點可以與其他有線網絡或者無線網絡連接，最后傳送到用戶終端。傳感器節點也可采用貪婪路由策略，即數據經最短距離傳送到匯聚節點。

1.2 小世界效應分析

假設已知普通節點Ni的平面坐標位置為（xi，yi），普通節點Nj位于（xj，yj），匯聚節點Sink的平面坐標位置為（xs，ys）。先計算普通節點Ni和Nj不經過超級節點把數據發送給匯聚節點的最短跳數距離為：

如圖1所示，如果普通節點Ni遠離匯聚節點，Ni先以無線多跳的方式將數據發送給最近的超級節點，超級節點通過超級鏈路直接傳送給匯聚節點。此時，Ni節點把數據發送給最近超級節點的最短跳數為：

當H（Ni， S）≥H' （Ni， S）時，節點選擇經超級節點發送數據。反之，當H（Nj，S）

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

其中：n為網絡中傳感器節點的個數；Hi-sink表示節點i到超級節點或匯聚節點的通信跳數距離，即為傳感器網絡中普通節點i到匯聚節點通信的所有路徑中最短傳輸路徑的跳數，表示為：

假設在同構網絡中加入μ個超級節點后，普通節點通過超級節點傳送數據的概率為ρi，μ，在一個大規模的無線傳感器網絡應用中，ρi，μ隨著μ值的增加而增大，則網絡節點到匯聚節點的路徑長度平均約為：

在初始的同構網絡中，沒有增設超級節點時，網絡節點到匯聚節點的平均路徑長度為：

所以，在同構Mesh網絡與通過增設μ個超級節點而構造生成的超級鏈路網絡之間，網絡節點到超級節點或匯聚節點的平均路徑長度的比率定義為平均路徑長度的變化率，記為：

在傳感器網絡中，節點的能量消耗主要用于數據處理與傳輸，所以網絡能耗與數據傳輸的平均路徑長度密切相關，定義能量節省比率為：

能量節省比率越大，表示傳感器網絡的能量效率越高。

對于增設了超級節點后的無線傳感器網絡，超級節點周圍的普通節點通過超級節點發送數據，網絡拓撲發生相應變化，網絡出現聚類特性，可認為具有較高的聚類系數。

1.3 仿真結果

仿真實驗采用規模為20×20的Mesh網絡，普通節點部署在Mesh網絡中的交叉點上，匯聚節點分別部署在（0，0）和網絡的中心（10，10）位置，假設超級節點同樣均勻部署在監測環境中，如圖2所示。

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

平均路徑長度變化率APLR（μ）與超級節點數的關系如圖4所示。在兩個模擬環境中都添加了6個超級節點，網絡的平均路徑長度減少約至45%。由曲線可知，若繼續增加超級節點的數量，路徑長度將不再顯著減少。因此，合理增加超級節點對網絡拓撲結構沒有太大影響，但可以大大減少數據傳輸的網絡路徑長度，進一步體現了小世界復雜網絡的特點。

網絡節能比率與增設超級節點的關系如圖5所示。當增加第1～6條超級鏈路時，網絡節能比率約50%，但增加更多超級鏈路后節能效果不明顯。且當匯聚節點位于（0，0）時，比位于（10，10） 時節能效果有明顯提高。

2 結 語

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

參考文獻

[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]張靜蓮，劉三陽，張朝輝.具有小世界現象的無線傳感器網絡構造方法[J].信號處理，2017，33（3）：417-421.

[13]周朝榮，徐小瓊，楊柳，等.基于小世界與能效的容遲網絡路由算法[J].電子科技大學學報，2016，45（1）：129-134.

[14]熊書明，胡永娣.基于小世界概念的異構傳感器網絡拓撲控制[J].計算機工程與設計，2016，37（11）：2869-2875.