摘  要： 在溫室、救災等環(huán)境監(jiān)測過程中，無線傳感器網絡會因頻繁發(fā)生自然故障和遭受惡意攻擊而引起網絡可生存性問題，針對這一問題提出了一種可自維護的具有抗毀性的拓撲控制算法。仿真結果表明，該算法能夠簡單有效地構建并維護容錯拓撲結構，在節(jié)點失效時保證網絡拓撲容錯抗毀，使得無線傳感器網絡具有可生存的能力。
關鍵詞： 無線傳感器網絡；容錯；拓撲控制

　無線傳感器網絡具有靈活部署的特點，非常適合應用于環(huán)境監(jiān)測、救災和軍事領域[1-2]。無線傳感器網絡一般具有規(guī)模大、自組織、隨機部署、環(huán)境復雜和節(jié)點資源有限等特點，這決定了拓撲控制在無線傳感器網絡研究中具有十分重要的作用。首先，拓撲控制能夠保證網絡的覆蓋質量和連通質量；其次，拓撲控制能夠降低通信干擾，提高MAC（Media Access Control）協(xié)議的效率，為數(shù)據(jù)融合和路由協(xié)議提供良好的拓撲基礎；此外，拓撲控制能夠提高網絡的可靠性和可擴展性等其他性能。因此，對無線傳感器網絡拓撲控制的研究具有十分重要的意義。特別是當用于溫室、救災等環(huán)境監(jiān)測時，節(jié)點的隨時開機和關機、無線裝置發(fā)送功率的變化、無線信道間的相互干擾以及自然故障和遭惡意攻擊引起的節(jié)點失效、鏈路故障頻繁發(fā)生，網絡拓撲隨時間頻繁變化。這就需要設計專門的可生存機制適應網絡結構的快速變化，以便通信能正常進行。因此利用拓撲控制技術設計容錯的拓撲結構是一個非常重要的網絡可生存研究課題[3]。
1 無線傳感器網絡拓撲控制算法現(xiàn)狀
　大量無線傳感器網絡的拓撲控制算法已經被提出，參考文獻[4]提出了LNT/LLT和LMN/LMA等基于節(jié)點度的算法，該算法給定了節(jié)點度的上限和下限需求，周期性動態(tài)調整節(jié)點的發(fā)射功率。參考文獻[5]提出了一種分布式計算RNG圖的算法。CBTC算法根據(jù)節(jié)點的方向性信號獲得本地信息構造拓撲[6]。參考文獻[7]提出了LMA算法，其基本思想是：給定鄰居節(jié)點個數(shù)的上限和下限，動態(tài)調整節(jié)點的發(fā)射功率，使得該節(jié)點的度數(shù)落在上限和下限內，其指出，如果每個節(jié)點的鄰居個數(shù)在范圍內就可以保證整個網絡的連通性。參考文獻[8]在LMA的基礎上，提出了K-Neigh算法，該算法對鄰居個數(shù)的范圍進行了研究，得到鄰居個數(shù)K值與網絡連通的關系。其進行了大量仿真實驗，當節(jié)點數(shù)n在50~500之間時，當最少鄰居個數(shù)K為9，則網絡以接近概率1連通；假如允許5%左右節(jié)點不連通，則最少鄰居個數(shù)為6。K-Neigh算法僅需距離信息，不需要知道鄰居節(jié)點的具體位置或方向信息。由于采用廣播的形式，分組能夠到達其發(fā)送半徑覆蓋范圍內的所有鄰居節(jié)點，采用物理層能量檢測技術和距離估計機制即可獲得K-Neigh算法所需的距離信息，不需要額外設備的支持。仿真實驗表明，K-Neigh算法在能耗和節(jié)點度等性能上都有提高。雖然K-Neigh算法簡單且實用，但是未考慮拓撲容錯問題[9-12]，會使得網絡可靠性無法保證，勢必帶來網絡的健壯性下降，不能有效處理節(jié)點、無線信道的失效以及多徑路由問題，這就需要考慮具有容錯特性的拓撲控制問題。
針對上述問題，本文提出了一種可自維護的無線傳感器網絡拓撲控制算法SMTC（Self-Maintainable Toplogy Control），并對該算法的性能進行了分析。
2 SMTC算法
　本文提出的拓撲控制算法SMTC具有自維護功能的容錯拓撲結構，該算法由信息收集、拓撲構建、功率設置和拓撲維護4個階段組成。
2.1 信息收集
　在信息收集階段，每個節(jié)點需要收集其最大發(fā)送半徑范圍內的節(jié)點信息。利用鄰節(jié)點發(fā)現(xiàn)協(xié)議[13]，各節(jié)點以最大功率周期性地廣播Hello包，Hello包中包括節(jié)點ID和位置信息，節(jié)點u在收集鄰近節(jié)點的Hello包后，構建近鄰節(jié)點列表，同時按照到近鄰節(jié)點的距離進行排序，在消息通告結束后，每個節(jié)點u獲得k最近鄰節(jié)點列表KN（u）。

2.4 拓撲維護
　在無線傳感器網絡運行過程中，自然環(huán)境和惡意攻擊引起的故障和失效會不斷發(fā)生，因此無線傳感器網絡必須具備持久抗毀的能力，否則一旦出現(xiàn)少量節(jié)點失效，而網絡又缺乏恢復的能力，就會降低網絡拓撲結構的可靠性，甚至會出現(xiàn)網絡拓撲分割的惡劣情況。因此，如何在檢測到節(jié)點失效時及時有效地重構網絡拓撲以恢復網絡的抗毀能力，是拓撲維護算法要解決的問題。使拓撲控制算法具備拓撲維護功能的具體過程如下：節(jié)點u在設置功率后，啟動KN（u）中所有鄰節(jié)點的定時器，每個節(jié)點以最大發(fā)送功率周期性地發(fā)送心跳包，確認連接是否正常。當節(jié)點u在收到其他鄰節(jié)點發(fā)送的心跳包后，重置KN（u）中該鄰節(jié)點的定時器。如果KN（u）中的某個鄰節(jié)點的定時器超時，則節(jié)點u認為網絡出現(xiàn)故障，節(jié)點u重新運行k鄰居拓撲控制算法的信息收集和功率設置步驟。這樣保證了節(jié)點重新連接新的k個最近鄰節(jié)點后，新的拓撲結構仍然是多連通的，維持了網絡拓撲的可靠性。
3 仿真與分析
　本文對SMTC算法生成的網絡拓撲結構的抗毀性進行仿真評估，研究其拓撲結構對于不同打擊模式的魯棒性和脆弱性。實驗假設網絡初始節(jié)點數(shù)n=300，它們隨機分布在1 000 m×1 000 m的區(qū)域中，去除的節(jié)點數(shù)占原始網絡總節(jié)點數(shù)的比例從0.1變化到0.8。在仿真中考慮了兩種情況：一是隨機故障，即完全隨機地去除網絡中的一部分節(jié)點；二是蓄意攻擊，有意識地去除網絡中一部分介數(shù)最高的節(jié)點?？梢杂米畲筮B通子圖的相對大小和剩余子圖的平均大小與失效節(jié)點比例的變化關系來度量網絡的魯棒性。圖1和圖2中數(shù)據(jù)是500次實驗的平均值，兩條曲線分別對應SMTC算法以及K-Neigh算法[15]生成的拓撲圖。
　圖1（a）和圖1（b）顯示了隨機故障情況下，最大連通子圖的相對大小和剩余子圖的平均大小與失效節(jié)點比例的關系曲線。

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

　從圖1和圖2可以看出，當失效節(jié)點比例較小時，SMTC算法生成的拓撲圖對于隨機故障和蓄意攻擊都具有極高的魯棒性。這種對少量節(jié)點失效的高度魯棒性，來自于網絡的高連通性。隨著失效節(jié)點比例的增加，生成的拓撲圖對于隨機故障和蓄意攻擊的容忍能力存在明顯的差異。與蓄意攻擊相比，網絡拓撲對于隨機節(jié)點故障拓撲結構具有良好的魯棒性，而除最大連通子圖外的其他子圖的平均大小的增長要緩慢很多。
　針對頻繁發(fā)生的自然故障和遭惡意攻擊引起的無線傳感器網絡可生存性問題，提出了一種可自維護的拓撲控制算法，該分布式算法能構建并維護容錯拓撲結構，且簡單、開銷小。仿真結果表明，在節(jié)點失效時，新的容錯拓撲控制算法能夠保證網絡的抗毀性，使得無線傳感器網絡具有持續(xù)可生存的能力。下一步的工作是研究認知網絡的自適應容錯拓撲控制技術。
參考文獻
[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 k-neigh protocol for symmetrie topology control in ad hoc networks[C]. Procedings of the 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] 殷人昆，陶永雷，謝若陽，等.數(shù)據(jù)結構[M].北京：清華大學出版社，1999.
[15] BLOUGH D M， LEONCINI M， RESTA G， et al. The k-neighbors approach to interference bounded and symmetric topology control in ad hoc networks[J]. IEEE Transactions on Mobile Computing， 2006，5（9）：1267-1282.