一種通過加入中繼節點以修復大面積網絡損壞的能量均衡算法

黃健文，倪衛明

0 引言

近年來，無線傳感網在學術與工程界均成為了研究熱點之一[1]。在太空探索、邊境防護、戰場偵察、環境監控等等領域有廣泛的應用。無線傳感網包含大量SN（Sensor Node：傳感節點），能夠在目標區域中對事件及其數據進行傳感與處理，并通過無線ad hoc網絡進行傳輸。但是，傳感節點具有有限的能量和傳輸范圍。且會因為極端的環境而產生大面積損壞，網絡被分割成若干不相連的分區，如圖1所示：

圖1 一種損壞了的WSN，分割成多個分區

多邊形圈外的節點即損壞節點，其把網絡分成了 3個分區。分區內實心圓點為分區的邊界點，小方框內圓點是邊界點中剩余能量最大的。在后文算法中有所應用。

這種情況下，大量文獻致力于研究如何修復網絡連通性。比如，可以通過重置其中某些節點的位置進行修復[2]；也可以通過加入RN(Relay Node：中繼節點)，輔助數據的傳輸與能量的優化[3]。一些啟發式算法致力于研究如何通過加入盡可能少的節點來進行修復。比如 CIST[4]（Connected Inter-Segment Topology：連通分區內拓撲）算法以 Steiner樹作為工具，采用的方法是：在每個分區邊界隨機選取一個rep（Representitive Node：代表節點），形成最小生成樹。以3個相鄰分區為單位，加入最少數量的RN，通過迭代修復連通性。其主要缺點是：網絡損壞后，由若干RN在單條鏈路上連通兩個分區，這些RN大多是割點，再次損壞概率很大。因此，蜘蛛網算法[5]（Spider-web Algorithm）對其進行改進，主要方法是：在每個分區隨機選擇一個節點作為代表，找到這些代表形成的凸包的中心點，各rep通過加入RN向中心節點靠攏，同時加入RN與左右鄰居rep連通。網絡的魯棒性有顯著提升，代價是增加了RN數量。

1 問題描述與基本模型

1.1 問題描述

需解決的問題描述如下：“在目標區域中給定n個不相連的傳感器分區，確定最少數量的RN以修復分區之間的連通性，并且考慮節點的剩余能量均衡性。”這個問題的最優解決方案為加入Steiner點，形成一棵最小Steiner樹。這里的Steiner點可以理解為RN。通常情況下，RN的主要功能是數據聚合和轉發。RN價格高，能量大，傳輸范圍大。但在本文中，假設所有節點的傳輸范圍相同，均為“R”。該問題可定義為SMT-MSP[6]（Steiner Minimum Tree with Minimum number of Steiner Points and bounded edge length：邊長受限、Steiner點數最小化的最小Steiner樹）問題，具體如下：

定義 1：SMT-MSP：給定節點組 V，傳輸范圍 R，SMT-MSP就是在V中形成一棵樹T，且加入的Steiner點數最少，T中的邊長均不超過R。

SMT-MSP問題是NP-hard問題。大量文獻致力于研究該問題，但大多較為關注如何減少RN數、提高覆蓋率、優化網絡拓撲等等，往往忽略了各節點能量均衡問題。

SMT-MSP的經典算法之一，以3-approximate為例，描述如下：找出所有可能性的邊，按邊長從小到大排列。若存在一個Steiner點可同時連接3個節點，則加上。再將剩余的邊上添加Steiner點完成連通。

1.2 系統模型

初始時，網絡由一組剩余能量不同、不可移動的SN組成，隨機分布在目標區域中。負責傳感周圍信息，處理數據并在傳感范圍內傳輸。SN和RN 具有相同的傳感范圍R。對每個節點Ni，其剩余能量為E(Ni)。由于不可抗力造成大面積節點損壞，網絡被分離成n個連通分區。在每個分區選出一個rep后，形成mst[8]（Minimum Spanning Tree：最小生成樹）。若兩個代表節點repi和repj之間在mst存在邊，則稱repi和repj為鄰居節點。同理，3個代表節點之間在mst中存在且只存在兩條邊，該3點也看作鄰居節點。本文不考慮其他鄰居情況。為連通若干rep所需加入的RN數量定義分為兩種，具體如下。這里，repi表示代表節點的編號，表示兩代表節點之間的距離。

a.連通兩個rep：

當需要連通3個rep時，會有兩種選擇。Wmst的情況如圖2所示：

圖2 通過mst連通分區

在兩條較短的鏈路添加Steiner點。Wf如圖3所示：

圖3 通過費馬點連通分區

先尋找3個節點的費馬點（Fermat Point）[9]。然后在連向費馬點的3條鏈路上添加Steiner點。

采取哪一種方式取決于所需Steiner點數的多少比較，即Gain值正負。Gain值定義為

本文也將節點的剩余能量納入考慮參數，采用經典的能量定義[10]如下。傳感能耗：Ps=α1per bit；發送能耗：Pt(r)=γ1+β*rαper bit；接收能耗：Pr=γ2per bit。式中，α1，γ1和γ2為常數，由底層技術決定。α是路徑損耗系數，取決于環境。β描述單位距離上傳輸單位bit信息所需的能量。

2 本文算法

下面介紹本文的算法流程。其偽代碼如圖4所示：

圖4 所提出算法的偽代碼

首先，網絡中的每個節點通過心跳信號維護一張表格，記錄鄰居節點的編號與位置。若節點失去鄰居節點信號，則將自己標記為邊界節點。各邊界節點運行洪泛算法將其位置與剩余能量信息告知各節點。蜘蛛網算法采用隨機抽取的方法選出每個分區的rep，CIST算法在分區邊界上隨機選擇。考慮到降低RN數量、均衡節點能量，所有節點默認將剩余能量最多的邊界節點看作該分區的rep。

步驟一：算法初始化

某個特殊的可移動節點巡邏得知各 rep位置與能量，由一能量不限的中心節點承擔計算任務，將rep形成mst。步驟二：迭代連通各分區

如圖5所示：

圖5 算法運行步驟說明

找出所有由3個節點組成的鄰居節點，并計算Gain。將 Gain按絕對值大小排列。選擇絕對值最大的一組添加Steiner點，Gain值為正則選擇費馬點方法；為負則選擇mst方法。如圖5(a)所示，第一輪迭代中選擇用費馬點方法連通S3,S4,S5。

由于能量的消耗與發送能耗直接相關且P rt∝ 。為均衡能耗，應使剩余能耗少的節點更靠近RN。如圖2，因為E (repi)＜ E(repj)，所以Steiner點從repj開始相隔R擺放。步驟三：更新節點狀態

首先，刪掉冗余鄰居節點。比如 S3無需再考慮與 S4連通，所以在下一輪迭代中無需考慮S3，S4，S6形成的鄰居節點。

為了進一步減少 RN數，充分利用新加入的 RN。若SN連接了RN，則其在之后的迭代中考慮由距離最近的RN代替的情況，計算新Gain。若可以減少需添加RN數，則采用替代方案。如圖5(b)，S3由R1代替，在后續迭代中完成與S1、S2連通。

需要說明的是，若發現網絡已不存在3個節點組成的鄰居，再考慮兩節點鄰居，并連通。如圖5(c)中的S7和S8。

3 相關證明

定理1：本文算法的時間復雜度為O(n3)。

證明：假設網絡分成 n個分區，首先采用 DD[11](Directed Diffusion：定向擴散路由協議)將邊界節點信息洪泛發送，時間復雜度為O(n)。由 mst性質可知，n個點形成的 mst有 e=n-1條邊。形成 mst的時間復雜度為O(elgn)=O((n-1)lgn)。在計算每組由 3個節點組成的鄰居所具有的Gain時，最壞情況是節點恰巧組成了星型網絡，存在=組。計算費馬點及RN位置可在固定時間內完成。節點擺放與狀態更新均可在固定時間內完成。因此，該算法的總時間復雜度為 O()，即O(n3)。

定理2：本文算法可保證網絡的連通性。

證明：采用反證法。假設算法的運行未完成網絡的連通，則至少存在一個分區，與其他分區分隔。在網絡尚未連通的情況下，就會運行偽代碼Procedure: Algorithm第七行的while循環。根據mst的定義，至少存在一個鄰居分區與該分區相連。根據while循環的步驟，可完成連通。

4 仿真結果

對提出的算法進行仿真，并將其性能與蜘蛛網算法、SMT-MSP算法進行比較。仿真環境為1000m*1200m平面。節點隨機產生。通過改變網絡規模，節點傳輸范圍來仿真所需RN數量的變化規律。所得結果是通過將算法運行50次取平均值得到的，且樣本值保持在均值15%區間范圍內。

4.1 不同網絡規模下需加入RN數量仿真

如圖6所示：

圖6 不同網絡規模下所需RN數曲線

比較了 3種算法在不同網絡規模下所需的 RN數量（假設傳輸距離R=100m）。

Spider-web算法所需RN數隨著分區數增加而大幅增加，這是因為分區數增多，就意味著節點離凸包中心點的距離增加，形成蜘蛛網所需的互聯節點增多。這需要大量的RN來完成。SMT-MSP算法與本文算法所需RN數也會隨分區數增加，這是因為分區增加意味著mst邊數增加，連通任務加大。

特定分區數下，Spider-web算法需要的RN數最大。這是因為該算法致力于優化網絡拓撲，并提高覆蓋率，減少割點。這是以增加 RN數為代價的。相對而言，經典的SMT-MSP算法僅以減少RN數為目標，在RN數上性能較優。本文提出的算法以減少RN數和均衡節點剩余能量為目標。通過mst方法、費馬點等方法減少RN數量。為了均衡節點能量，剩余能量較多的節點會承擔更多的連通過任務。RN替代的方法進一步減少RN數量。所以，本文的該項性能上有了進一步提升。

如圖7所示：

圖7 不同傳輸范圍下所需RN數曲線

比較了不同傳輸范圍情況下的所需RN數（假設分區數=9）。也得到了相似的結論。傳輸范圍增加有利于分區互聯，所以所需RN數隨之減少。

4.2 能量仿真

本文仿真了網絡中剩余 SN數隨時間的變化情況。假設α1=60 *10-9J/bit，γ1=45 *10-9J/bit ，γ2=135 *10-9J/bit。設為α=2。當α=2時， β=10 *10-12J/ bit/m2。假設傳感節點每隔1s進行一次傳感，任何節點的傳輸數據量取決于拓撲結構，且單位數據量為2bit。仿真考慮兩種路由：a.SPR(Shortest Path Routing：最短路徑路由)，以距離為邊的權值。b.EBR(Energy Balancing Routing：最優能耗路由)，綜合考慮鏈路通信能耗與節點剩余能耗[12]。網絡規模設置如下：存在10個SN，傳輸范圍為50。新節點的初始能量為0.1J，但算法開始運行時，假設網絡已工作一段時間，SN剩余能量各不相同，RN剛被加入網絡。在每個時間點所得的數值是通過取 50次平均值所得，且樣本值保持在均值15%區間范圍內。

如圖8所示：

圖8 存活SN隨時間變化曲線

當第一個RN能量耗盡時，網絡停止運轉。首先，采用不同的路由方式對網絡生命有一定的影響。EBR方式路由將節點剩余能量以及收發能耗作為權值，能耗較大的節點、能耗較小的鏈路會承擔更多的傳輸任務。而SPR方式路由以距離為權值。所以無論哪種算法，EBR方式路由均在網絡生命上優于 SPR方式路由。其次，本文提出的算法在網絡能耗上優于SMT-MSP 3-App算法。這是因為本文在rep選擇上考慮了能耗，且在之后的拓撲上采用RN代替SN進行傳輸等均衡能耗的方法。

5 結束語

本文研究了無線傳感網出現大面積損壞節點時的連通性修復問題，在 CIST, Spider-web算法的基礎上，以減少RN數，均衡各節點剩余能量為目標提出了新的算法。在算法中，采用了最小生成樹，Steiner點，費馬點等經典方法減少RN數量。且剩余能量較多的邊界節點、RN節點承擔更多的傳輸任務，以均衡網絡節點的剩余能量。仿真結果顯示該算法可以以加入較少RN節點且維護網絡能量均衡。

[1]Chong.C.Y, Kumar.S.P.Sensor networks: Evolution,opportunities, and challenges[C]//Proc.of IEEE.[s.n.].2003:1247-1256.

[2]Younis.M, Lee.S, Gupota.S,et al.A Localized Self-healing Algorithm for Networks of Moveable Sensor Nodes[C]// Proc.Conf.GLOBECOM.New Orleans:[s.n.].2008:1-5.

[3]Lee.S, Younis.M.Optimized Relay Placement to Federate Segments in Wireless Sensor Networks[J].IEEE On Selected Areas in Commun., 2011,28(5):742-752.

[4]Senel.F,Younis.M.Optimized Connectivity Restoration in a Partitioned Wireless Sensor Network[C]// Proc.Conf.GLOBECOM.Houston: [s.n.].2011:1-5.

[5]Senel.F, Younis.M, Akkaya.K.A Robust Relay Node Placement Heuristic for Structurally Damaged Wireless Sensor Networks[C]// Proc.Conf.Local Computer Networks.Switzerland: [s.n.].2009:20-23.

[6]Chen.D.H, Du.D.Z, Hu.X.D,et al.Approximations for Steiner Trees with Minimum Number of Steiner Points[J].Journal of Global Optimization., 2000,18:17-33.

[7]Cheng.X.Z, Du.D.Z, Wang.L.S.[C]Relay Sensor Placement in Wireless Sensor Networks

[8]Ruzika.S,Hamacher.H.W.A Survey on Multiple Objective Minimum Spanning Tree Problems[J].Algorithmics of Large and Complex Networks., 2009, 5515:104-116.

[9]Shay.G, Ran.T., The Fermat-Steiner Problem[J].The American Mathematical Monthly., 2002,109(5): 443-451.

[10]Sun.D, Shayman.M.Prolonging Network Lifetime via Partially Controlled Node Deployment and Adaptive Data Propagation in WSN[C]//Proc.Conf.Information Sciences and Systems.Baltimore: [s.n.].2007:226-231.

[11]張錦,林亞平,李超等.傳感器網絡中基于角度域的洪泛路由算法[J].計算機工程與科學, 2005,27(9):59-71.

[12]Bechkit.M, Koudil.M, Challal.Y, et al.A New Weighted Shortest Path Tree for Convergecast Traffic Routing in WSN[C]//Proc.Conf.Computers and Communications.Cappadocia: [s.n.].2012:187-192.