一種可自維護(hù)的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?

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

（佳木斯大學(xué) 理學(xué)院，黑龍江 佳木斯 154007）

無線傳感器網(wǎng)絡(luò)具有靈活部署的特點(diǎn)，非常適合應(yīng)用于環(huán)境監(jiān)測、救災(zāi)和軍事領(lǐng)域[1-2]。無線傳感器網(wǎng)絡(luò)一般具有規(guī)模大、自組織、隨機(jī)部署、環(huán)境復(fù)雜和節(jié)點(diǎn)資源有限等特點(diǎn)，這決定了拓?fù)淇刂圃跓o線傳感器網(wǎng)絡(luò)研究中具有十分重要的作用。首先，拓?fù)淇刂颇軌虮ＷC網(wǎng)絡(luò)的覆蓋質(zhì)量和連通質(zhì)量；其次，拓?fù)淇刂颇軌蚪档屯ㄐ鸥蓴_，提高 MAC（Media Access Control）協(xié)議的效率，為數(shù)據(jù)融合和路由協(xié)議提供良好的拓?fù)浠A(chǔ)；此外，拓?fù)淇刂颇軌蛱岣呔W(wǎng)絡(luò)的可靠性和可擴(kuò)展性等其他性能。因此，對無線傳感器網(wǎng)絡(luò)拓?fù)淇刂频难芯烤哂惺种匾囊饬x。特別是當(dāng)用于溫室、救災(zāi)等環(huán)境監(jiān)測時，節(jié)點(diǎn)的隨時開機(jī)和關(guān)機(jī)、無線裝置發(fā)送功率的變化、無線信道間的相互干擾以及自然故障和遭惡意攻擊引起的節(jié)點(diǎn)失效、鏈路故障頻繁發(fā)生，網(wǎng)絡(luò)拓?fù)潆S時間頻繁變化。這就需要設(shè)計專門的可生存機(jī)制適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)的快速變化，以便通信能正常進(jìn)行。因此利用拓?fù)淇刂萍夹g(shù)設(shè)計容錯的拓?fù)浣Y(jié)構(gòu)是一個非常重要的網(wǎng)絡(luò)可生存研究課題[3]。

1 無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ìF(xiàn)狀

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

針對上述問題，本文提出了一種可自維護(hù)的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴⊿MTC（Self-Maintainable Toplogy Control），并對該算法的性能進(jìn)行了分析。

2 SMTC算法

本文提出的拓?fù)淇刂扑惴⊿MTC具有自維護(hù)功能的容錯拓?fù)浣Y(jié)構(gòu)，該算法由信息收集、拓?fù)錁?gòu)建、功率設(shè)置和拓?fù)渚S護(hù)4個階段組成。

2.1 信息收集

在信息收集階段，每個節(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)列表，同時按照到近鄰節(jié)點(diǎn)的距離進(jìn)行排序，在消息通告結(jié)束后，每個節(jié)點(diǎn)u獲得k最近鄰節(jié)點(diǎn)列表 KN（u）。

2.2 拓?fù)錁?gòu)建

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

2.3 功率設(shè)置

每個節(jié)點(diǎn)以最大發(fā)送功率通告其k最近鄰節(jié)點(diǎn)列表，在收到其他節(jié)點(diǎn)發(fā)送的近鄰節(jié)點(diǎn)列表后，每個節(jié)點(diǎn)進(jìn)行有向邊雙向化處理，更新KN（u）。根據(jù)參考文獻(xiàn)[15]中的定理2，不經(jīng)過拓?fù)溥厡ΨQ化處理仍然能保證網(wǎng)絡(luò)高概率連通。最后，節(jié)點(diǎn)設(shè)置其發(fā)送功率僅覆蓋到KN（u）中距離自己最遠(yuǎn)的鄰節(jié)點(diǎn)。

2.4 拓?fù)渚S護(hù)

在無線傳感器網(wǎng)絡(luò)運(yùn)行過程中，自然環(huán)境和惡意攻擊引起的故障和失效會不斷發(fā)生，因此無線傳感器網(wǎng)絡(luò)必須具備持久抗毀的能力，否則一旦出現(xiàn)少量節(jié)點(diǎn)失效，而網(wǎng)絡(luò)又缺乏恢復(fù)的能力，就會降低網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的可靠性，甚至?xí)霈F(xiàn)網(wǎng)絡(luò)拓?fù)浞指畹膼毫忧闆r。因此，如何在檢測到節(jié)點(diǎn)失效時及時有效地重構(gòu)網(wǎng)絡(luò)拓?fù)湟曰謴?fù)網(wǎng)絡(luò)的抗毀能力，是拓?fù)渚S護(hù)算法要解決的問題。使拓?fù)淇刂扑惴ň邆渫負(fù)渚S護(hù)功能的具體過程如下：節(jié)點(diǎn) u在設(shè)置功率后，啟動 KN（u）中所有鄰節(jié)點(diǎn)的定時器，每個節(jié)點(diǎn)以最大發(fā)送功率周期性地發(fā)送心跳包，確認(rèn)連接是否正常。當(dāng)節(jié)點(diǎn)u在收到其他鄰節(jié)點(diǎn)發(fā)送的心跳包后，重置KN（u）中該鄰節(jié)點(diǎn)的定時器。如果 KN（u）中的某個鄰節(jié)點(diǎn)的定時器超時，則節(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個最近鄰節(jié)點(diǎn)后，新的拓?fù)浣Y(jié)構(gòu)仍然是多連通的，維持了網(wǎng)絡(luò)拓?fù)涞目煽啃浴?/p>

3 仿真與分析

本文對SMTC算法生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的抗毀性進(jìn)行仿真評估，研究其拓?fù)浣Y(jié)構(gòu)對于不同打擊模式的魯棒性和脆弱性。實(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)；二是蓄意攻擊，有意識地去除網(wǎng)絡(luò)中一部分介數(shù)最高的節(jié)點(diǎn)。可以用最大連通子圖的相對大小和剩余子圖的平均大小與失效節(jié)點(diǎn)比例的變化關(guān)系來度量網(wǎng)絡(luò)的魯棒性。圖1和圖2中數(shù)據(jù)是500次實(shí)驗(yàn)的平均值，兩條曲線分別對應(yīng)SMTC算法以及KNeigh算法[15]生成的拓?fù)鋱D。

圖1（a）和圖 1（b）顯示了隨機(jī)故障情況下，最大連通子圖的相對大小和剩余子圖的平均大小與失效節(jié)點(diǎn)比例的關(guān)系曲線。

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

從圖1和圖2可以看出，當(dāng)失效節(jié)點(diǎn)比例較小時，SMTC算法生成的拓?fù)鋱D對于隨機(jī)故障和蓄意攻擊都具有極高的魯棒性。這種對少量節(jié)點(diǎn)失效的高度魯棒性，來自于網(wǎng)絡(luò)的高連通性。隨著失效節(jié)點(diǎn)比例的增加，生成的拓?fù)鋱D對于隨機(jī)故障和蓄意攻擊的容忍能力存在明顯的差異。與蓄意攻擊相比，網(wǎng)絡(luò)拓?fù)鋵τ陔S機(jī)節(jié)點(diǎn)故障拓?fù)浣Y(jié)構(gòu)具有良好的魯棒性，而除最大連通子圖外的其他子圖的平均大小的增長要緩慢很多。

針對頻繁發(fā)生的自然故障和遭惡意攻擊引起的無線傳感器網(wǎng)絡(luò)可生存性問題，提出了一種可自維護(hù)的拓?fù)淇刂扑惴?，該分布式算法能?gòu)建并維護(hù)容錯拓?fù)浣Y(jié)構(gòu)，且簡單、開銷小。仿真結(jié)果表明，在節(jié)點(diǎn)失效時，新的容錯拓?fù)淇刂扑惴軌虮ＷC網(wǎng)絡(luò)的抗毀性，使得無線傳感器網(wǎng)絡(luò)具有持續(xù)可生存的能力。下一步的工作是研究認(rèn)知網(wǎng)絡(luò)的自適應(yīng)容錯拓?fù)淇刂萍夹g(shù)。

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

[2]石軍鋒，鐘先信，陳帥，等.無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)及特點(diǎn)分析[J].重慶大學(xué)學(xué)報（自然科學(xué)版），2005，28（2）：16-19.

[3]路綱，周明天，牛新征，等.無線網(wǎng)絡(luò)鄰近圖綜述[J].軟件學(xué)報，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]時銳，劉宏偉，董劍，等.自組織容錯拓?fù)淇刂频难芯縖J].電子學(xué)報，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ù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，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.