一種可自維護的無線傳感器網絡拓撲控制算法*

王艷麗，侯憲春，王志林，王東方，宋可凡

（佳木斯大學 理學院，黑龍江 佳木斯 154007）

無線傳感器網絡具有靈活部署的特點，非常適合應用于環境監測、救災和軍事領域[1-2]。無線傳感器網絡一般具有規模大、自組織、隨機部署、環境復雜和節點資源有限等特點，這決定了拓撲控制在無線傳感器網絡研究中具有十分重要的作用。首先，拓撲控制能夠保證網絡的覆蓋質量和連通質量；其次，拓撲控制能夠降低通信干擾，提高 MAC（Media Access Control）協議的效率，為數據融合和路由協議提供良好的拓撲基礎；此外，拓撲控制能夠提高網絡的可靠性和可擴展性等其他性能。因此，對無線傳感器網絡拓撲控制的研究具有十分重要的意義。特別是當用于溫室、救災等環境監測時，節點的隨時開機和關機、無線裝置發送功率的變化、無線信道間的相互干擾以及自然故障和遭惡意攻擊引起的節點失效、鏈路故障頻繁發生，網絡拓撲隨時間頻繁變化。這就需要設計專門的可生存機制適應網絡結構的快速變化，以便通信能正常進行。因此利用拓撲控制技術設計容錯的拓撲結構是一個非常重要的網絡可生存研究課題[3]。

1 無線傳感器網絡拓撲控制算法現狀

大量無線傳感器網絡的拓撲控制算法已經被提出，參考文獻[4]提出了LNT/LLT和LMN/LMA等基于節點度的算法，該算法給定了節點度的上限和下限需求，周期性動態調整節點的發射功率。參考文獻[5]提出了一種分布式計算RNG圖的算法。CBTC算法根據節點的方向性信號獲得本地信息構造拓撲[6]。參考文獻[7]提出了LMA算法，其基本思想是：給定鄰居節點個數的上限和下限，動態調整節點的發射功率，使得該節點的度數落在上限和下限內，其指出，如果每個節點的鄰居個數在范圍內就可以保證整個網絡的連通性。參考文獻 [8]在LMA的基礎上，提出了K-Neigh算法，該算法對鄰居個數的范圍進行了研究，得到鄰居個數K值與網絡連通的關系。其進行了大量仿真實驗，當節點數n在50～500之間時，當最少鄰居個數K為9，則網絡以接近概率1連通；假如允許5%左右節點不連通，則最少鄰居個數為6。K-Neigh算法僅需距離信息，不需要知道鄰居節點的具體位置或方向信息。由于采用廣播的形式，分組能夠到達其發送半徑覆蓋范圍內的所有鄰居節點，采用物理層能量檢測技術和距離估計機制即可獲得K-Neigh算法所需的距離信息，不需要額外設備的支持。仿真實驗表明，K-Neigh算法在能耗和節點度等性能上都有提高。雖然K-Neigh算法簡單且實用，但是未考慮拓撲容錯問題[9-12]，會使得網絡可靠性無法保證，勢必帶來網絡的健壯性下降，不能有效處理節點、無線信道的失效以及多徑路由問題，這就需要考慮具有容錯特性的拓撲控制問題。

針對上述問題，本文提出了一種可自維護的無線傳感器網絡拓撲控制算法SMTC（Self-Maintainable Toplogy Control），并對該算法的性能進行了分析。

2 SMTC算法

本文提出的拓撲控制算法SMTC具有自維護功能的容錯拓撲結構，該算法由信息收集、拓撲構建、功率設置和拓撲維護4個階段組成。

2.1 信息收集

在信息收集階段，每個節點需要收集其最大發送半徑范圍內的節點信息。利用鄰節點發現協議[13]，各節點以最大功率周期性地廣播Hello包，Hello包中包括節點ID和位置信息，節點u在收集鄰近節點的Hello包后，構建近鄰節點列表，同時按照到近鄰節點的距離進行排序，在消息通告結束后，每個節點u獲得k最近鄰節點列表 KN（u）。

2.2 拓撲構建

在信息收集完成后，每個節點u可以建立其最大功率拓撲結構，用一個無向有權圖=（V（u），E（u））來表示，其中 V（u）=KN（u）∪{u}。 節點 u 在得到了最大功率拓撲圖后，執行Dijkstra算法[14]求出以它為根的最短路徑樹。為了保證中所有的邊都能存在于最終拓撲圖中，u分別記錄每個中間節點v的兒子節點集合，記為 SNu（v），并通過 Hello 消息將集合 SNu（v）告知節點v，也就是希望u的鄰居節點v必須和節點集SNu（v）相連，從而保證了 u到每個節點的路徑都存在于最終的拓撲圖中。

2.3 功率設置

每個節點以最大發送功率通告其k最近鄰節點列表，在收到其他節點發送的近鄰節點列表后，每個節點進行有向邊雙向化處理，更新KN（u）。根據參考文獻[15]中的定理2，不經過拓撲邊對稱化處理仍然能保證網絡高概率連通。最后，節點設置其發送功率僅覆蓋到KN（u）中距離自己最遠的鄰節點。

2.4 拓撲維護

在無線傳感器網絡運行過程中，自然環境和惡意攻擊引起的故障和失效會不斷發生，因此無線傳感器網絡必須具備持久抗毀的能力，否則一旦出現少量節點失效，而網絡又缺乏恢復的能力，就會降低網絡拓撲結構的可靠性，甚至會出現網絡拓撲分割的惡劣情況。因此，如何在檢測到節點失效時及時有效地重構網絡拓撲以恢復網絡的抗毀能力，是拓撲維護算法要解決的問題。使拓撲控制算法具備拓撲維護功能的具體過程如下：節點 u在設置功率后，啟動 KN（u）中所有鄰節點的定時器，每個節點以最大發送功率周期性地發送心跳包，確認連接是否正常。當節點u在收到其他鄰節點發送的心跳包后，重置KN（u）中該鄰節點的定時器。如果 KN（u）中的某個鄰節點的定時器超時，則節點u認為網絡出現故障，節點u重新運行k鄰居拓撲控制算法的信息收集和功率設置步驟。這樣保證了節點重新連接新的k個最近鄰節點后，新的拓撲結構仍然是多連通的，維持了網絡拓撲的可靠性。

3 仿真與分析

本文對SMTC算法生成的網絡拓撲結構的抗毀性進行仿真評估，研究其拓撲結構對于不同打擊模式的魯棒性和脆弱性。實驗假設網絡初始節點數n=300，它們隨機分布在1 000 m×1 000 m的區域中，去除的節點數占原始網絡總節點數的比例從0.1變化到0.8。在仿真中考慮了兩種情況：一是隨機故障，即完全隨機地去除網絡中的一部分節點；二是蓄意攻擊，有意識地去除網絡中一部分介數最高的節點?？梢杂米畲筮B通子圖的相對大小和剩余子圖的平均大小與失效節點比例的變化關系來度量網絡的魯棒性。圖1和圖2中數據是500次實驗的平均值，兩條曲線分別對應SMTC算法以及KNeigh算法[15]生成的拓撲圖。

圖1（a）和圖 1（b）顯示了隨機故障情況下，最大連通子圖的相對大小和剩余子圖的平均大小與失效節點比例的關系曲線。

圖2（a）和圖 2（b）顯示了蓄意攻擊情況下，最大連通子圖的相對大小和剩余子圖的平均大小與失效節點比例的關系曲線。

從圖1和圖2可以看出，當失效節點比例較小時，SMTC算法生成的拓撲圖對于隨機故障和蓄意攻擊都具有極高的魯棒性。這種對少量節點失效的高度魯棒性，來自于網絡的高連通性。隨著失效節點比例的增加，生成的拓撲圖對于隨機故障和蓄意攻擊的容忍能力存在明顯的差異。與蓄意攻擊相比，網絡拓撲對于隨機節點故障拓撲結構具有良好的魯棒性，而除最大連通子圖外的其他子圖的平均大小的增長要緩慢很多。

針對頻繁發生的自然故障和遭惡意攻擊引起的無線傳感器網絡可生存性問題，提出了一種可自維護的拓撲控制算法，該分布式算法能構建并維護容錯拓撲結構，且簡單、開銷小。仿真結果表明，在節點失效時，新的容錯拓撲控制算法能夠保證網絡的抗毀性，使得無線傳感器網絡具有持續可生存的能力。下一步的工作是研究認知網絡的自適應容錯拓撲控制技術。

[1]SANTI P.Topology control in wireless ad hoc and sensor networks[J].ACM Comp.Surveys，2005，37（2）：164-194.

[2]石軍鋒，鐘先信，陳帥，等.無線傳感器網絡結構及特點分析[J].重慶大學學報（自然科學版），2005，28（2）：16-19.

[3]路綱，周明天，牛新征，等.無線網絡鄰近圖綜述[J].軟件學報，2008，19（4）：888-911.

[4]RAMANATHAN R，ROSALES H R.Topology control of multihop wireless networks using transmit power adjustment[C].Proceedings of IEEE INFOCOM，2002：404-413.

[5]JAROMCZYK J W，TOUSSAINT G T.Relative neighborhood graphs and their relatives[J].Proceedings of the IEEE， 1992，80（9）： 1502-1517.

[6]LI L， HALPERM J Y， BAHL P， et al.Analysis of a cone-based distributed topology control algorithm for wireless multi-hop Networks[C].Proceedings of ACM Symposium on Principles of Distributed Computing（PODC），2001：264-273.

[7]KUVISEH M， KARL H， WOLISZ A， et al.Distributed algorithm for transmission power control in wireless sensor networks[C].IEEE Wireless Communication and Networking WCNC， 2003（1）：558-563.

[8]BLOUGH D， LEONCINI M， RESTA G， et al.The kneigh protocol for symmetrie topology control in ad hoc networks[C].Procedingsofthe 4th ACM International Symposium on Mobile Ad Hoc Networking&Computing，2003：141-152.

[9]時銳，劉宏偉，董劍，等.自組織容錯拓撲控制的研究[J].電子學報，2005，3（11）：1978-1982.

[10]Li Xiangyang， Wan Pengjun， Wang Yu， et al.Fault tolerant deployment and topology control in wireless networks[C].Proceedings of Fourth ACM Symposium on Mobile Ad Hoc Networking and Computing（MOB IHOC），2003：117-128.

[11]LI N， HOU J C.FLSS： a fault-tolerant topology control algorithm for wireless networks[C].Proceedings of the 10th Annual International Conference on Mobile Computing and Networking（MOB ICOM），2004： 275-286.

[12]BAHRAMGIRI M，HAJIAGHAYI M，MIRROKNI V S.Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks[C].Proceedings of 11th International Conference on Computer Comm and Networks （ ICCCN）， 2002： 392-397.

[13]OGIER R，LEWIS M，TEMPLIN F.Topology dissemination based on reverse-path forwarding （TBRPF）[S].MANET Internet Draft，2003.

[14]殷人昆，陶永雷，謝若陽，等.數據結構[M].北京：清華大學出版社，1999.

[15]BLOUGH D M，LEONCINI M，RESTA G，et al.The kneighbors approach to interference bounded and symmetric topology control in ad hoc networks[J].IEEE Transactions on Mobile Computing， 2006，5（9）：1267-1282.