一種通過加入中繼節(jié)點以修復(fù)大面積網(wǎng)絡(luò)損壞的能量均衡算法

黃健文，倪衛(wèi)明

0 引言

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

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

多邊形圈外的節(jié)點即損壞節(jié)點，其把網(wǎng)絡(luò)分成了 3個分區(qū)。分區(qū)內(nèi)實心圓點為分區(qū)的邊界點，小方框內(nèi)圓點是邊界點中剩余能量最大的。在后文算法中有所應(yīng)用。

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

1 問題描述與基本模型

1.1 問題描述

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

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

SMT-MSP問題是NP-hard問題。大量文獻致力于研究該問題，但大多較為關(guān)注如何減少RN數(shù)、提高覆蓋率、優(yōu)化網(wǎng)絡(luò)拓撲等等，往往忽略了各節(jié)點能量均衡問題。

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

1.2 系統(tǒng)模型

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

a.連通兩個rep：

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

圖2 通過mst連通分區(qū)

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

圖3 通過費馬點連通分區(qū)

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

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

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

2 本文算法

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

圖4 所提出算法的偽代碼

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

步驟一：算法初始化

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

如圖5所示：

圖5 算法運行步驟說明

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

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

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

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

需要說明的是，若發(fā)現(xiàn)網(wǎng)絡(luò)已不存在3個節(jié)點組成的鄰居，再考慮兩節(jié)點鄰居，并連通。如圖5(c)中的S7和S8。

3 相關(guān)證明

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

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

定理2：本文算法可保證網(wǎng)絡(luò)的連通性。

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

4 仿真結(jié)果

對提出的算法進行仿真，并將其性能與蜘蛛網(wǎng)算法、SMT-MSP算法進行比較。仿真環(huán)境為1000m*1200m平面。節(jié)點隨機產(chǎn)生。通過改變網(wǎng)絡(luò)規(guī)模，節(jié)點傳輸范圍來仿真所需RN數(shù)量的變化規(guī)律。所得結(jié)果是通過將算法運行50次取平均值得到的，且樣本值保持在均值15%區(qū)間范圍內(nèi)。

4.1 不同網(wǎng)絡(luò)規(guī)模下需加入RN數(shù)量仿真

如圖6所示：

圖6 不同網(wǎng)絡(luò)規(guī)模下所需RN數(shù)曲線

比較了 3種算法在不同網(wǎng)絡(luò)規(guī)模下所需的 RN數(shù)量（假設(shè)傳輸距離R=100m）。

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

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

如圖7所示：

圖7 不同傳輸范圍下所需RN數(shù)曲線

比較了不同傳輸范圍情況下的所需RN數(shù)（假設(shè)分區(qū)數(shù)=9）。也得到了相似的結(jié)論。傳輸范圍增加有利于分區(qū)互聯(lián)，所以所需RN數(shù)隨之減少。

4.2 能量仿真

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

如圖8所示：

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

當(dāng)?shù)谝粋€RN能量耗盡時，網(wǎng)絡(luò)停止運轉(zhuǎn)。首先，采用不同的路由方式對網(wǎng)絡(luò)生命有一定的影響。EBR方式路由將節(jié)點剩余能量以及收發(fā)能耗作為權(quán)值，能耗較大的節(jié)點、能耗較小的鏈路會承擔(dān)更多的傳輸任務(wù)。而SPR方式路由以距離為權(quán)值。所以無論哪種算法，EBR方式路由均在網(wǎng)絡(luò)生命上優(yōu)于 SPR方式路由。其次，本文提出的算法在網(wǎng)絡(luò)能耗上優(yōu)于SMT-MSP 3-App算法。這是因為本文在rep選擇上考慮了能耗，且在之后的拓撲上采用RN代替SN進行傳輸?shù)染饽芎牡姆椒ā?/p>

5 結(jié)束語

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

[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]張錦,林亞平,李超等.傳感器網(wǎng)絡(luò)中基于角度域的洪泛路由算法[J].計算機工程與科學(xué), 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.