基于ＴｏｐＤｉｓｃ算法的ＷＳＮ拓撲控制研究

（華北電力大學 計算機科學與技術學院， 河北 保定 071003）



摘要：

針對TopDisc算法構建的網絡靈活性不強、重復執行算法的開銷大、未考慮節點的剩余能量等問題，對其進行改進，并利用OPNET網絡仿真工具進行了模擬。分析結果表明改進的TopDisc算法比原有算法有更好的節能性與穩定性。

關鍵詞：無線傳感器網絡; 拓撲控制； 分簇； TopDisc

中圖分類號：TP393文獻標志碼：A

文章編號：10013695(2009)03100104



Study on WSN’s topology control based on TopDisc algorithm



ZHU Yongli， CHEN Tao



(School of Computer Science Technology， North China Electric Power University， Baoding Hebei 071003， China)



Abstract:

Aiming at the shortcomings and problems of the TopDisc algorithm that the flexibility of the building network was not strong， repeating the implementation of the algorithm cost too much and not considering the remaining nodes energy. This paper introduced an improved algorithm on the base of TopDisc and made great improvement to make it more stable. Used the OPNET network tool to carry on the simulation. The analysis results prove that the improved TopDisc algorithm has better energy conservation and stability compared with the original one.

Key words：WSN; topology control; clustering; TopDisc



0引言

無線傳感器網絡(wireless sensor networks， WSN)是由一組稠密布置、隨機分布的傳感器構成的無線自組織網絡[1~3]，其目的是協作地感知、采集和處理網絡覆蓋的地理區域內感知對象的信息，并發布給觀察者。文獻[4]中指出，在未來將會對人類的生存方式產生巨大影響的新興技術有十種，而無線傳感器網絡名列十種新技術之首。對于自組織的無線傳感器網絡而言，網絡拓撲控制對網絡性能影響很大[5]，提高路由協議和MAC協議的效率，為數據融合、時間同步和目標定位等很多方面提供基礎，有利于延長整個網絡的生存時間。所以拓撲控制是傳感器網絡中的一個基本問題[1，6]，它是傳感器網絡中諸多其他研究課題的基礎。

在傳感器網絡中，網絡的拓撲結構控制與優化有著十分重要的意義，主要表現在以下幾個方面[7，8]:a）影響整個網絡的生存時間;b)減少節點間通信干擾，提高網絡通信效率;c)為路由協議提供基礎;d)影響數據融合;e)彌補節點失效的影響。傳感器網絡拓撲控制研究的主要問題是[9]：在滿足網絡覆蓋度和連通度的前提下，通過功率控制和骨干網節點選擇，剔除節點之間不必要的通信鏈路，形成一個數據轉發的優化網絡結構。

本文針對TopDisc分簇拓撲算法的缺點進行了改進，并用OPNET軟件進行了仿真，結果表明改進的算法在網絡性能和網絡生存周期方面比原算法更優良。

1TopDisc算法的分析及缺點

利用無線通信的廣播性，Deb等人提出了一種節能的拓撲發現算法[10]（TopDisc)。TopDisc算法利用顏色來區分節點狀態，解決骨干網絡拓撲結構的形成問題。因此，TopDisc算法屬于層次性拓撲控制算法。 TopDisc算法提出了兩種具體的節點狀態標記方法，分別稱為三色算法和四色算法。這兩種算法有兩個相同點，即利用顏色標記理論找到簇首節點及利用與傳輸距離成反比的延時，使得一個黑色節點(即簇首節點)覆蓋更大的區域。TopDisc算法繼承了圖論中的經典算法[11]，是早期成簇算法的代表，可以使節點在密部署的傳感器網絡中快速地形成分簇結構，并在簇頭之間建立樹型關系。但是由于此算法建成的網絡靈活性不強，重復執行算法的開銷過大，另外算法也沒有考慮節點的剩余能量問題。

DuboisFerries等人提出了基于Voronoi簇的多匯聚點TopDisc的擴展算法[12]，這個算法為每一個簇都指定了一個匯聚點，用于從簇中獲取數據。每個普通節點都記錄與它最近的匯聚點的信息以及它到該匯聚點的距離，當一個信息到達一個匯聚點時，數據識別模塊檢查該包的傳輸距離是否比當前的最近匯聚點的距離更近。如果更近，該普通節點便更新其最近匯聚點并廣播該信息。普通節點也可轉發來自與當前最近匯聚點距離同樣近的數據包。這個算法的一個缺陷就是未考慮節點的剩余能量問題。

2TopDisk算法的改進

2.1算法模型

本算法是在TopDisc算法的基礎上進行了改進的一種多匯聚節點算法，用于不同環境下的無線傳感器節點以及無線傳感器網絡有不同的屬性。因此首先對傳感器節點及網絡作如下場景的假設:

a)所有的sink node都有可持續提供的能源和充足的內存與計算資源。Sink node是發起拓撲發現的節點，也是管理整個網絡運行的節點，sink node的處理能力、存儲能力和通信能力相對較強，它可以連接Internet等外部網絡，實現兩種協議棧之間的轉換，同時發布管理節點的監測任務，并把收集的數據轉發到外部網絡上。

b)每個sink node和傳感器節點都是固定不動的，它們之間靠無線鏈路進行通信。

c)傳感器節點的能量是有限的，每傳輸一個數據包，節點就減少一部分能量。設定傳輸中消耗的能量與數據包的字節數成正比，與傳輸距離的立方成正比。

d)在運行改進的TopDisc算法前，無線傳感器已經通過時間同步算法的運行實現了網絡內傳感器節點的同步，為后面的計算時間差做準備。

e)每個節點都可以產生、復制、轉發數據包。節點在單位時間內產生數據的可能性為p。

f)信道的傳輸方式為雙工方式。

具有全雙工信道傳輸方式的無線傳感器網絡可以被抽象為一個無向圖G=(V， E)，如式（1）所示。其中：V是所有普通無線傳感器節點和匯聚點的集合；E是所有鄰接點之間鏈路的集合。兩個節點相鄰，是指每個節點都在對方的信號覆蓋范圍內。從而有

V=Vsink∪Vsensor，E={(i，j)|i，j∈V}(1)

每一個普通節點的初始電量設為Emax，路徑的數學描述形式為｛V1，V2，…，Vi，Vj，…，S｝，Vi，Vj∈Vsensors，S∈Vsink。可將鏈路開銷定義為一條鏈路〈Vi，Vj〉的開銷（link cost， LC）為

LCij=α×d3+β(2)

其中：α為無線傳感器節點無線通信模塊每發送1 bit至1 m遠的地方所需耗費的電量， β為無線傳感器節點用于接收并放大1 bit所需耗費的電量，d為兩個無線傳感器節點間的距離。

2.2算法的改進

算法的實現過程分為四個階段，下面分別詳細介紹這四個階段的實現過程。

a)拓撲發現。本算法在TopDisc拓撲構建算法四色算法的基礎上做了很大的修改。（a）TopDisc四色算法中每個黑色節點的覆蓋范圍是該節點的最大傳輸范圍，而在本算法中黑色節點的覆蓋范圍半徑為其最大覆蓋范圍半徑的2/5，原因將在簇內分級中詳細敘述。（b)拓撲發現請求是由各匯聚點單獨發起的，因此每個傳感器節點都保存有到各個匯聚點的路徑，并按匯聚點編號排序，以便原路徑因節點電量過低而失效，從而切換路徑時所有普通節點都向同一個新的匯聚點發送信息。（c）拓撲發現過程中排除電量過低不適合做簇首的節點。（d）每個簇相對于簇外看來可認為是一個節點，因此在拓撲發現請求傳遍整個網絡后，整個網絡形成一個以簇首節點為骨干網節點，各匯聚點為根的多棵樹。隨后，只有簇首將反向查找信息向上層簇首發送。該原理的示意圖如圖1所示。



其中，A是簇首節點，C和D是以A為簇首的普通節點。對于B發送消息，只有A對B作應答，C和D不應答，應答消息集成了包括C和D收集到的消息在內的消息。

拓撲發現過程結束后，無線傳感器網絡的各個簇首節點形成了以匯聚點為根節點的生成樹，有幾個匯聚點，就會有幾棵生成樹。當一個簇內的首節點因電量過低等原因需要更換時，需要將更換消息告訴父簇首節點和所有孩子簇首節點，因此每個簇首節點都需要保留其父簇首節點和子簇首節點的信息。

由于各個匯聚點獨立地創建以自己為根的生成樹，無線傳感器網絡中一個節點在以匯聚點為S1的生成樹中是簇首節點，但在S2中可能就是普通節點。一個普通節點可能同時屬于多于一個的簇和生成樹，因此普通節點還要保存有多個簇首節點和匯聚點的信息，以便原路徑失效時能將它收集到的數據傳送到其他匯聚點。然而，在同一時刻只有一棵生成樹有效，即同一時刻所有簇首節點僅將數據傳送到一個匯聚點。在無線傳感器節點內將至不同匯聚點的路徑排序，只有當這棵生成樹失效時才更換其他路徑。圖2展示了匯聚點S1在拓撲發現執行前和執行后的拓撲變化過程。

b)簇內分級。無線傳感器網絡拓撲結構生成之后，簇內各節點向對應的簇首節點發送數據，簇首節點再將收集到的數據向父簇首節點發送，直至發送到當前工作的匯聚點。為了讓各簇首節點間能直接通信，設無線傳感器節點最大覆蓋半徑為R，簇首節點的覆蓋半徑不能超過R/2。由式(2)可知，兩個節點間傳送數據的開銷與兩點間的距離的立方成正比。

原來經過1跳傳輸以最大覆蓋半徑傳輸時消耗的能量為

LCij=α×R3+β

現在需經過兩跳，消耗的能量為

LC′ij=2[α×(R/2)3+β]

顯然由α和β的物理意義可知β=α， 因此有LCij＜LC′ij。

雖然減小簇首節點的覆蓋半徑增加了網絡內的簇首節點數目，但能在一定程度上減小能量消耗。對于無線傳感器網絡而言，節能是最重要的，因此這種以犧牲響應時間換取能耗的策略還是可取的。當簇首節點因電量低而不能再承擔簇首節點的任務時，就會觸發簇內分級過程的運行。簇內各節點發送簇內的廣播消息，收到消息的簇內節點立即發送應答消息，簇首節點根據應答消息的時延可知簇內各節點與它之間的距離，簇首節點將與它的距離分為小于R/10及大于R/10小于2R/5兩組，如圖3所示。

c)拓撲維護。 將簇內節點分組后，距簇首節點的距離小于R/10的節點將作為備用簇首節點。當原簇首節點電量過低時，就從備用簇首節點中挑選電量最大的節點作為新的簇首節點，并將簇內信息和網絡拓撲告知新簇首節點。新的簇首節點會根據原簇首節點發過來的信息通知所有簇內節點，并將新簇首節點的信息通知父簇首節點和子簇首節點。直至當前匯聚點的拓撲樹失效或此新的簇首節點死亡，父簇首節點和子簇首節點都與這個新簇首通信。

d)拓撲切換。在拓撲維護過程中，當原簇首節點因電量低失效時，如果發現在其R/10覆蓋范圍內沒有其他備用簇首傳感器節點或所有傳感器節點都小于閾值時，便向父簇首節點發送拓撲切換消息，父簇首節點再向上傳遞該消息，直至匯聚點，匯聚點記錄失效簇。當匯聚點發現失效簇過多時，就向整個無線傳感器網絡發布拓撲失效信息，該消息向全網絡廣播后，網絡中的各簇首節點轉而沿第二個匯聚點的生成樹流向對應的匯聚點。若所有的匯聚點構成的拓撲樹都失效，網絡便停止運行。圖4演示了拓撲切換過程；圖5為改進后算法流圖。

3算法仿真及結果分析

采用OPNET網絡仿真工具對改進的TopDisk算法進行仿真，在100 m×100 m的區域內，放置了40個無線傳感器節點。節點隨機分布于指定區域內，每個節點的信號覆蓋半徑為15 m。其中有兩個匯聚點分布于網絡的兩端，假設信道的傳輸誤碼率為0。

假設節點的初始電量為1，每發送或轉發一個包所消耗的電量為0.04(假設發送和轉發一個包需耗費的電量相同)，同時假設電量小于0.2時節點標記為死亡。設置節點死亡后可轉發數據，但不再產生數據；節點電量為0時不再轉發數據；每個簇內設置2~3個節點以供當前簇首節點死亡后更換其他節點為新簇首節點。

圖6 為原始的TopDisc算法和改進的TopDisc算法的死亡節點數量隨時間變化的情況。其中，（a）為改進前的TopDisc算法中死亡節點數量隨時間的變化圖；（b）為改進后死亡節點數量隨時間變化圖。

由圖可以看出，從第50 min左右開始出現節點死亡現象。截至仿真結束前，原始的TopDisc算法的死亡節點數量在8~9，改進后的TopDisc算法的死亡節點數在7~8，改進后節點死亡數量有一定程度的減少。這是因為在原始TopDisc算法中，網絡拓撲結構一旦確定，直至網絡癱瘓，同一節點一直扮演普通節點或簇首節點，而簇首節點由于既要發送數據又要轉發數據，比普通節點耗電量大，尤其是越靠近匯聚點的簇首節點轉發的數據越多，電量耗費也越大，節點死亡越快。而在改進的TopDisc算法中，由于簇首節點的即時更換和網絡拓撲結構切換后，同一節點在有的樹中擔任普通節點，而在其他樹中擔任匯聚點，且在不同的樹中，與根節點的距離也不同，耗電量也有差別，使得能耗在網絡節點間均衡消耗，從而減少了死亡節點數量。

圖7為原始的TopDisc算法和改進的TopDisc算法中整個網絡的吞吐率。其中，(a)為改進前網絡的吞吐率；(b)為改進后網絡的吞吐率。由圖可以看出原始的TopDisc算法的網絡吞吐率穩定在1 250 bps左右，改進后的TopDisc算法的網絡吞吐率穩定在1 750 bps左右，改進后算法的網絡吞吐率有所提高。這是因為在原始的TopDisc算法中，網絡拓撲結構一旦確定，直至網絡癱瘓，同一節點自始至終扮演普通節點或簇首節點中的一個角色，而簇首節點既要發送數據，又要轉發數據，所以比普通節點耗電量大，尤其是越靠近匯聚點的簇首節點轉發的數據越多，電量耗費也越大，網絡的使用壽命越低。而在改進的TopDisc算法中，由于簇首節點的即時更換和網絡拓撲結構切換，使得能耗在網絡中的節點間均衡消耗，使網絡的平均吞吐率有了增加。

4結束語

傳感器網絡一直受到國內外學者的廣泛關注，而拓撲結構控制是傳感器網絡的關鍵技術之一，本文對網絡的拓撲結構控制進行了研究與仿真。由數據分析可知，雖然原始的TopDisc算法中數據包的平均跳數要比改進后算法的平均跳數小，但在網絡整體吞吐率和死亡節點數量這兩項統計數據中，改進的TopDisc算法比原始TopDisc算法都有明顯的提高，因此改進的算法延長了網絡的生存壽命，提高了網絡的吞吐率。

參考文獻：

[1]張學，陸桑璐，陳貴海，等.無線傳感器網絡的拓撲控制[J].軟件學報， 2007， 18(4):943954.

[2]湯波，羅昌俊.DSCO: 無線傳感器網絡分簇拓撲結構的研究[J].計算機應用研究， 2007， 24(10):315317.

[3]趙保華， 張煒， 劉恒昌，等.無線傳感器網絡中的組劃分算法[J].計算機學報， 2006， 29(1):161165.

[4]10 emerging technologies that will change the world[EB/OL].(200402). http://www.technologyreview.com/articles/print_version/erging0203.asp.10

[5]ROMER K， MATTERN F.The design space of wireless sensor networks[J]. Wireless Communications， 2004，11(6):5461.

[6]滑楠，史浩山.無線傳感器網絡動態簇組織算法研究[J].計算機應用研究， 2007， 24(7):16161619.

[7]陳積明， 林瑞仲， 孫優賢.無線傳感器網絡通信體系研究[J].傳感技術學報， 2006， 19(4):12901295.

[8]PAN Jianping， Hou Y T， CAI Lin， et al. Topology control for wireless sensor networks[C]//Proc of the 9th Annual International Conference on Mobile Computing and Networking. New York: ACM Press， 2003:286299.

[9]AKYILDIZ I F， SU W， CAYIRCI E. et al. A survey on sensor networks[J]. IEEE Communications Magazine， 2002，40(8):102114.

[10]DEB B， BHATANGR S， NATHh B. A topology discovery algorithm for sensor networks with applications to network management， DCSTR441[R]. Piscataway:Rutgers University， 2001.

[11]BAO Lichun， GARCIALUNAACEVES J J. Topology management in Ad hoc networks[C]//Proc of 4th the ACM International Symposium on Mobile Ad hoc Networking and Computing. New York: ACM Press， 2003:129140.

[12]DUBOISFERRIERE H， ESTRIN D， STATHOPOULOS T. Efficient and practical query scoping in sensor networks[C]//Proc of IEEE International Conference on Mobile Ad hoc and Senser System. 2004:564566.

[13]HE Yanxiang， ZENG Yuan. Interferenceaware topology control problem in wireless sensor networks[C]// Proc of the 6th International Conference on ITS Telecommunications. 2006:969972.