摘  要： 在溫室、救災(zāi)等環(huán)境監(jiān)測(cè)過(guò)程中，無(wú)線傳感器網(wǎng)絡(luò)會(huì)因頻繁發(fā)生自然故障和遭受惡意攻擊而引起網(wǎng)絡(luò)可生存性問(wèn)題，針對(duì)這一問(wèn)題提出了一種可自維護(hù)的具有抗毀性的拓?fù)淇刂?/a>算法。仿真結(jié)果表明，該算法能夠簡(jiǎn)單有效地構(gòu)建并維護(hù)容錯(cuò)拓?fù)浣Y(jié)構(gòu)，在節(jié)點(diǎn)失效時(shí)保證網(wǎng)絡(luò)拓?fù)淙蒎e(cuò)抗毀，使得無(wú)線傳感器網(wǎng)絡(luò)具有可生存的能力。
關(guān)鍵詞： 無(wú)線傳感器網(wǎng)絡(luò)；容錯(cuò)；拓?fù)淇刂?/p>

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

2.4 拓?fù)渚S護(hù)
　在無(wú)線傳感器網(wǎng)絡(luò)運(yùn)行過(guò)程中，自然環(huán)境和惡意攻擊引起的故障和失效會(huì)不斷發(fā)生，因此無(wú)線傳感器網(wǎng)絡(luò)必須具備持久抗毀的能力，否則一旦出現(xiàn)少量節(jié)點(diǎn)失效，而網(wǎng)絡(luò)又缺乏恢復(fù)的能力，就會(huì)降低網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的可靠性，甚至?xí)霈F(xiàn)網(wǎng)絡(luò)拓?fù)浞指畹膼毫忧闆r。因此，如何在檢測(cè)到節(jié)點(diǎn)失效時(shí)及時(shí)有效地重構(gòu)網(wǎng)絡(luò)拓?fù)湟曰謴?fù)網(wǎng)絡(luò)的抗毀能力，是拓?fù)渚S護(hù)算法要解決的問(wèn)題。使拓?fù)淇刂扑惴ň邆渫負(fù)渚S護(hù)功能的具體過(guò)程如下：節(jié)點(diǎn)u在設(shè)置功率后，啟動(dòng)KN（u）中所有鄰節(jié)點(diǎn)的定時(shí)器，每個(gè)節(jié)點(diǎn)以最大發(fā)送功率周期性地發(fā)送心跳包，確認(rèn)連接是否正常。當(dāng)節(jié)點(diǎn)u在收到其他鄰節(jié)點(diǎn)發(fā)送的心跳包后，重置KN（u）中該鄰節(jié)點(diǎn)的定時(shí)器。如果KN（u）中的某個(gè)鄰節(jié)點(diǎn)的定時(shí)器超時(shí)，則節(jié)點(diǎn)u認(rèn)為網(wǎng)絡(luò)出現(xiàn)故障，節(jié)點(diǎn)u重新運(yùn)行k鄰居拓?fù)淇刂扑惴ǖ男畔⑹占凸β试O(shè)置步驟。這樣保證了節(jié)點(diǎn)重新連接新的k個(gè)最近鄰節(jié)點(diǎn)后，新的拓?fù)浣Y(jié)構(gòu)仍然是多連通的，維持了網(wǎng)絡(luò)拓?fù)涞目煽啃浴?br /> 3 仿真與分析
　本文對(duì)SMTC算法生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的抗毀性進(jìn)行仿真評(píng)估，研究其拓?fù)浣Y(jié)構(gòu)對(duì)于不同打擊模式的魯棒性和脆弱性。實(shí)驗(yàn)假設(shè)網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)n=300，它們隨機(jī)分布在1 000 m×1 000 m的區(qū)域中，去除的節(jié)點(diǎn)數(shù)占原始網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的比例從0.1變化到0.8。在仿真中考慮了兩種情況：一是隨機(jī)故障，即完全隨機(jī)地去除網(wǎng)絡(luò)中的一部分節(jié)點(diǎn)；二是蓄意攻擊，有意識(shí)地去除網(wǎng)絡(luò)中一部分介數(shù)最高的節(jié)點(diǎn)?？梢杂米畲筮B通子圖的相對(duì)大小和剩余子圖的平均大小與失效節(jié)點(diǎn)比例的變化關(guān)系來(lái)度量網(wǎng)絡(luò)的魯棒性。圖1和圖2中數(shù)據(jù)是500次實(shí)驗(yàn)的平均值，兩條曲線分別對(duì)應(yīng)SMTC算法以及K-Neigh算法[15]生成的拓?fù)鋱D。
　圖1（a）和圖1（b）顯示了隨機(jī)故障情況下，最大連通子圖的相對(duì)大小和剩余子圖的平均大小與失效節(jié)點(diǎn)比例的關(guān)系曲線。

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

　從圖1和圖2可以看出，當(dāng)失效節(jié)點(diǎn)比例較小時(shí)，SMTC算法生成的拓?fù)鋱D對(duì)于隨機(jī)故障和蓄意攻擊都具有極高的魯棒性。這種對(duì)少量節(jié)點(diǎn)失效的高度魯棒性，來(lái)自于網(wǎng)絡(luò)的高連通性。隨著失效節(jié)點(diǎn)比例的增加，生成的拓?fù)鋱D對(duì)于隨機(jī)故障和蓄意攻擊的容忍能力存在明顯的差異。與蓄意攻擊相比，網(wǎng)絡(luò)拓?fù)鋵?duì)于隨機(jī)節(jié)點(diǎn)故障拓?fù)浣Y(jié)構(gòu)具有良好的魯棒性，而除最大連通子圖外的其他子圖的平均大小的增長(zhǎng)要緩慢很多。
　針對(duì)頻繁發(fā)生的自然故障和遭惡意攻擊引起的無(wú)線傳感器網(wǎng)絡(luò)可生存性問(wèn)題，提出了一種可自維護(hù)的拓?fù)淇刂扑惴ǎ摲植际剿惴軜?gòu)建并維護(hù)容錯(cuò)拓?fù)浣Y(jié)構(gòu)，且簡(jiǎn)單、開(kāi)銷(xiāo)小。仿真結(jié)果表明，在節(jié)點(diǎn)失效時(shí)，新的容錯(cuò)拓?fù)淇刂扑惴軌虮ＷC網(wǎng)絡(luò)的抗毀性，使得無(wú)線傳感器網(wǎng)絡(luò)具有持續(xù)可生存的能力。下一步的工作是研究認(rèn)知網(wǎng)絡(luò)的自適應(yīng)容錯(cuò)拓?fù)淇刂萍夹g(shù)。
參考文獻(xiàn)
[1] SANTI P. Topology control in wireless ad hoc and sensor networks[J]. ACM Comp. Surveys，2005，37（2）：164-194.
[2] 石軍鋒，鐘先信，陳帥，等．無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)及特點(diǎn)分析[J]．重慶大學(xué)學(xué)報(bào)（自然科學(xué)版），2005，28（2）：16-19.
[3] 路綱，周明天，牛新征，等．無(wú)線網(wǎng)絡(luò)鄰近圖綜述[J]．軟件學(xué)報(bào)，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] 時(shí)銳，劉宏偉，董劍，等.自組織容錯(cuò)拓?fù)淇刂频难芯縖J].電子學(xué)報(bào)，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] 殷人昆，陶永雷，謝若陽(yáng)，等.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，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.