基于能量與功率控制的TopDisc拓撲算法研究

謝 昕，張 恒，于忠平，周 娟

(華東交通大學信息工程學院，江西南昌330013)

在無線傳感器網絡中體系結構，網絡拓撲控制[1-5]具有十分重要的意義。設計良好的拓撲控制結構能夠提高路由協議和MAC協議的效率，為數據融合、時間同步、目標定位等很多方面提供基礎，有利于延長整個網絡的生存時間。

傳感器網絡中的拓撲控制按照研究方向可以分為兩類:節點功率控制和層次型拓撲控制組織[6-9]。其中，節點功率控制中的本地平均算法(LMA[10])通過動態調整節點的發射功率來形成拓撲結構;其主要思想是通過定期廣播一個包含自己ID的LifeMsg消息，并為鄰居節點設置一個上下限，當鄰居數小于下限時，就增大發射功率;當大于上限時，就減弱發射功率。LMA算法也存在一些問題，它缺少嚴格的理論推導，在鄰居節點的判斷條件上沒有嚴格的說明。層次型拓撲控制方面的TopDisc[11-12]算法是由Deb等人提出的一種基于圖論中最小支配集問題的經典算法。TopDisc算法利用顏色來描述節點狀態，解決骨干網拓撲結構的形成問題。TopDisc算法中提出兩種節點標記方法，分別為三色算法和四色算法。這兩種方法的區別在于，四色算法中，節點多了一種深灰色狀態的節點，從而使得兩種算法在形成簇后的結構有所不同。四色算法能形成比三色算法更少的簇，且簇與簇之間的交疊更少;但四色算法相對于三色算法可能會形成一些孤獨的黑色節點，它不覆蓋灰色節點。兩種算法的核心思想都是:利用顏色標記理論找到簇頭節點;利用與傳輸距離成反比的延時，使得一個黑色節點(簇頭節點)覆蓋更大的范圍。該算法可以在節點密集的傳感器網絡中快速的形成分簇結構，并在簇于簇之間建立樹型關系。但是由于這種算法構建成的層次型網絡的靈活性不強，重復執行算法的開銷過大，且該算法沒有考慮到節點的剩余能量問題。

本文主要思想是在TopDisc算法的基礎上，通過引入能量、功率控制機制，動態地改變節點發射功率，形成一種不等規模的簇型結構，減少簇與簇之間的交疊范圍，從而使得簇間工作更加獨立，減少了簇間的相互干擾。

1 網絡模型定義

1.1 節點定義

定義1 所有節點都有唯一的編號，即ID信息。

定義2 整個網絡中存在一個sink節點，該節點的數據處理和通信能力高于其他節點。有較強的數據收集和節點檢測、查詢能力，且該節點有持續的能源供給，并可以把數據傳輸到外部網絡。

定義3 假設節點能夠知道自己本身的位置，且位置固定。在數據傳輸時，附帶自己的位置信息，使它的鄰居節點和簇頭節點都知道它的位置。

定義4 節點除了進行本簇內的數據收集和數據傳輸外，在必要時候，還必須兼顧簇間數據傳輸任務。

定義5 除sink節點外，所有節點的初始能量相同，設為Emax，傳輸中消耗的能量和所傳輸的字節成正比，和傳輸的距離也成正比。耗能公式為E(d)=kαdn

(1)

其中，k為常數，α代表傳輸的字節大小，n滿足關系2＜n＜4，n的取值與很多因素有關，如地理情況，信號干擾等，考慮到這些因素，通常n的取值為3;d代表兩節點間的距離。

定義6 傳感器節點具有功率控制能力，假設節點的功率控制范圍是[0，F]，F為最大發射功率，所有節點開始都在最大發射功率F下工作，此時的發射半徑為R。

定義7 所有節點都知道自身的當前剩余能量，記為:En。在進行數據傳輸時，附帶其剩余能量信息，是簇頭節點知道它的剩余能量。

定義8 給傳感器節點設置一個能量閥值E min，當傳感器節點的能量低于這個閥值時，傳感器不能被選為簇頭節點，但可以傳輸數據，直到節點能量耗盡。

定義9 傳感器節點狀態分為5個狀態，分別為睡眠、空閑、監聽、發送和接受狀態。其中規定睡眠狀態不消耗能量，其余狀態在單位時間內都消耗一定的能量。

1.2 網絡定義

定義1 無線傳感器網絡可抽象為一個無向圖G{V，E}，V代表頂點，即無線傳感器節點的集合;E代表邊，即相鄰節點之間鏈路的集合。可描述為

其中，我們設C為所有的簇頭節點集合，Vi代表節點i的鄰居信息，i∈C。

定義2 在整個網絡的生存期來說，因簇頭的選舉和功率控制機制導致的網絡拓撲結構變化所消耗的能量，可以忽略不記。

2 基于能量與功率控制的改進算法

2.1 簇頭節點與簇內節點

網絡起始階段，所有節點都標記為白色節點，都處于活動狀態，由sink節點發起TopDisc算法的三色算法。此階段因為是開始階段，所有節點的能量都相同，不必考慮能量問題，其過程和三色算法一樣。當一個節點被選為簇頭節點時，該節點記錄下此時的自身能量信息Enc。三色算法執行完之后，所有簇內節點向簇首節點發送帶有與簇首節點距離長度的消息，消息發送完成后無任務的灰色節點立即進入睡眠狀態，設定時間ts1和ts2，并在時間ts1過后醒來監聽簇首節點消息，并向簇首節點發送帶有自身剩余能量的信息，時間ts2后又進入睡眠狀態，如果在ts2超時前簇首節點有消息任務需要其傳送，立即變為活動節點。當簇內進行簇頭選舉時，節點被選舉為簇頭節點的概率為

其中:l為常數，En和Emax分別為節點的當前剩余能量和節點的初始最大能量。

2.2 簇的形成與更新

簇內節點經過第一輪三色算法后，形成了網絡的初始拓撲結構(見圖1)。從圖1中可以看出，簇間的交疊范圍比較大，增加了簇間傳遞數據沖突的發生概率，干擾了簇間數據的有效傳遞。

為了降低簇間傳遞數據發生沖突的概率，引入了節點功率控制機制，動態的調節節點的發射功率，其主要思想為:因為簇頭節點都知道簇內節點的具體位置，所以簇頭節點可以通過控制發射功率的大小來改變自身的發射半徑，達到減少簇間交疊范圍的作用。節點的功率控制范圍是[0，F]。如圖2所示，Dab表示節點a到節點b的距離，Dbc表示節點b到節點c的距離，因為Dab＞Dbc，所以我們選擇調節節點c的發射功率，發射功率調節滿足下面公式

其中:m為常數，m的取值在[0，1]之間，取值根據實際情況而定;R為最大發射半徑。圖3為圖2經過功率控制機制后的更新圖。

從圖3可以看出，簇間的交疊減少，他們之間包含的灰色節點也相應的減少。通過節點功率控制機制，我們得到圖1更新后的網絡拓撲結構，如圖4。

從圖4可以看出，簇間的交疊和簇間包含的灰色節點減少的更加明顯，從而大大降低了簇間通信發生沖突的概率。

2.3 簇的維護

網絡拓撲結構穩定之后，為確保簇間通信有效的維持下去，還要對拓撲結構進行維護，起維護過程包括兩個方面。

第一:當簇頭節點的當前能量滿足(6)式時，要選擇新的簇頭節點。其中:En代表節點的當前剩余能量;Enc代表節點被選為簇頭時，記錄下來的能量。

圖1 網絡初始拓撲結構

圖2 無功率機制

圖3 通過功率機制

圖4 更新后網絡拓撲結構

第二:新的簇頭節點的選擇需要滿足時延機制。時延機制可表示為(7)式，其中:C1和C2代表常數;dy表示該節點到當前簇頭節點的距離;Ey表示該節點當前自身的剩余能量。

通過時延機制選出新的簇頭節點，并通過功率控制機制，更新網絡拓撲結構，最終回到網絡拓撲穩定階段。

3 算法仿真及結果分析

本文用MATLAB作為仿真平臺，在200m×200m的區域內，隨機地散布了200個傳感器節點，規定每個傳感器初始能量都為1。在工作半小時后，隨機地抽取其中100個節點，并記錄下剩余能量值。圖5為兩種算法剩余能量的比較圖，從圖5中可以看出，改進后算法的能量分布更加的均勻，原因是節點被輪流選為簇頭節點。TopDisc算法沒有考慮到節點的剩余能量問題，所以出現了部分節點死亡;改進后算法的節點剩余能量遠遠大于原TopDisc算法，主要原因是通過了功率控制機制，間接地降低了節點的發射功率大小，節省了節點的多余能量開銷。

圖5 改進后算法與原TopDisc算法剩余能量比較

圖6 改進后算法與原TopDisc算法生命周期比較

圖6為兩種算法的生命周期的比較，改進后算法因為節點輪流的來做簇頭節點，且通過功率控制機制對節點的發射功率進行控制，生命周期有顯著地提高，直到2 000秒才出現死亡節點;相對于原TopDisc算法，沒有出現在同一時刻，節點的急劇死亡，節點數量的變化比較平穩;而原TopDisc算法，隨著時間的推移，節點死亡的速度也加快。

4 結束語

本文在TopDisc三色算法基礎上，提出一種基于能量與功率控制的拓撲算法。通過實驗仿真發現，改進后的算法在節點能耗的控制上，具有明顯的效果，減少了簇間的交疊范圍，使得簇間通信更加獨立，降低了簇間通信發生沖突的概率，提高了整個網絡的生命周期。本文側重于改進算法的理論研究，但在實際應用中可能還會遇到很多的問題，下一步的研究重點將放到實際應用中，從而完善算法在實際應用的不足。

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

[2] 楊賀，張樹東，孫利民.無線傳感器網絡的拓撲控制[J].計算機科學，2007，34(1):36-38.

[3] LIL，HALPERN JY，BAHL P.Analysis of a cone-based distributed topology control algorithm forwirelessmu lti-hop networks[C].In:Proc ACM Sym p on Principles of Distributed Computing(PODC)，Acm，Newport，RI，2001:264-273.

[4] AMISA D，PRAKASH R，VUONGTHP.MaxMin d-cluster formation inwirelessad hoc Networks[C].In:Proc IEEEConfon Computer Communications(INFOCOM)，IEEE.1999:32-41.

[5] 孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京:清華大學出版社，2005.

[6] 陳力軍，毛鶯池，陳道蓄，等.平均度約束的無線傳感器網絡拓撲控制[J].計算機學報，2007，30(9):1 044-1 050.

[7] WEIY，HEIDEMANN J，ESTRIN D.An energy-efficientMAC protocol forwireless sensornetworks[J].Scientific Research Publishing，2008(1):59-69.

[8] 唐小軍，曹長修，譚燕.無線傳感器網絡基于能量效率的分布式拓撲控制[J].計算機應用，2007，27(6):207-209.

[9] ZHU J，ZHAOH，XU JQ.An energy balanced reliable routingmetric in WSNs[J].Scientific Research Publishing，2009(1):22-26.

[10] KUBISCH M，KARLH，WOLISZ A.Distributed algorithms for transmission power controlinwireless sensornetworks[C].IEEEWCNC 2003，New Orleans，Louisiana，IEEE，2003:16-20.

[11] DEB B，BHATNAGARS，NATH B.A topology discovery algorithm for sensor networkswith applications to network management[J].DCSTechnical Report DCS-TR-411，Rutgers University，2001(5):26-30.

[12] CHANDRA R，FETZERC，HOGSTEDTK.Adaptive topology discovery in hybridwireless networks[C].Proceedingsin Informatics，1st International Conference on Ad-hoc Networks andWireless，Toronto，2002:356-359.