異構無線傳感器網絡中繼節點部署算法

馬千里,袁 易,申朝暉

(1.山西大學 計算機與信息技術學院,太原 030006; 2.太原歐亞科技發展有限公司,太原 030006)

0 概述

無線傳感器網絡(Wireless Sensor Networks,WSNs)由近千個傳感器節點組成,每個傳感器節點由電池提供能量,傳感器節點通常部署于環境惡劣的地方,這導致節點可能發生失效,從而影響整個網絡的連通質量[1]。針對該問題,在傳感器節點網絡中引入中繼節點,傳感器節點不再直接將信息發送給彼此,而是先發送給中繼節點,然后中繼節點再將信息發送給其他傳感器節點,進而實現網絡信息的傳遞。這與引入actor節點使網絡連通的無線傳感器和執行器網絡(Wireless Sensor and Actor Networks,WSANs)工作原理類似[2]。actor節點可移動且較sensor節點通信性能更好,若傳感器節點因意外或者電量耗盡而失效,actor節點可代替失效節點工作,并能較好地適應網絡的隨機變化。根據相關部署策略引入中繼節點的部署方案,實質上與在異構網絡中增加具有較高通信性能的actor節點類似。

LIN等人[3]最早在WSNs中添加中繼節點,將同構網絡中加入最少中繼節點的問題命名為最少數目斯坦納點和有界邊長的斯坦納樹問題(Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge Length,STP-MSPBEL)并證明其為NP難問題,在此基礎上,提出基于圖增量的中繼節點部署GA-RD算法。文獻[4]對GA-RD算法進行改進,提出基于權重圖的IWGA-RD算法,并證明該算法具有更好的近似比。算法的近似比和近似解反映了算法優化程度,在改進算法部署時其可作為衡量算法能否減少節點數量和提高網絡性能的參考指標。

目前,WSNs中繼節點數據傳輸包括自主收集、接收信息、攜帶信息后再發送等環節,使全網數據吞吐量與傳輸量大幅提升。為滿足傳感器網絡數據吞吐量和傳輸量的要求,網絡部署規模龐大且節點眾多而密集,在節點收發信息的瞬時易造成網絡擁塞,甚至導致網絡癱瘓。因此,減少傳感器網絡中繼節點數量至關重要。本文在IWGA-RD算法的基礎上進行改進,提出一種基于節點權重與邊長的LWGA算法,通過對節點權重和邊長的排序改進中繼節點加入網絡的優先級次序,以選擇傳感器網絡中節點數量更少的中繼節點部署方式。

1 研究現狀

無線傳感器網絡作為一種重要的網絡技術,將信息世界與人們日常生活緊密聯系在一起,實現了兩者之間的交互。WSNs以數據為中心,其中傳感器節點由感知、數據處理及存儲、通信、供能單元構成[5-6]。WSNs技術與其應用場景關聯密切,不同場景的應用技術有較大差別。WSNs因其大規模、自組織、高可靠性等特點被廣泛應用于軍事、醫療、環境等領域,但是由于其存在節點能量易耗盡造成網絡中斷、存儲空間有限等缺點,因此研究人員將精力集中在WSNs有利特性的研究[7-9]上。目前關于WSNs的研究方向為傳感器的網絡連通、網絡節能[10-11]以及網絡覆蓋[12-14]等方面,本文主要研究傳感器網絡環境下中繼節點部署的網絡連通問題。

研究人員從上世紀末就開始對在網絡中添加中繼節點進行研究。文獻[3]所提STP-MSPBEL方案中最小Steiner樹[15]和最小生成樹問題類似,都是最短網絡的一種解決方案,但兩者區別在于,最小生成樹網絡是在給定的點集和邊中尋求最短網絡使網絡連通,而最小Steiner樹網絡允許在給定的點之外增加額外點使網絡連通[16]。

本文主要研究基于Steiner樹的網絡。在文獻[3]的基礎上,研究人員對這類問題進行改進和優化。文獻[17]基于文獻[3]重新推導算法的近似比,證明該算法的近似比為4。文獻[18]提出一種使網絡達到k-連通的中繼節點部署算法。文獻[19]證明使網絡達到連通加入最少異構中繼節點的問題仍為NP難問題,并對文獻[3]所提中繼節點部署算法的近似比重新推導得到近似比為7。文獻[20]基于文獻[19]提出結合約束部署區域的思想新算法,將近似比降低到2。上述算法均基于網絡中節點為同構這一假設,即要求加入的中繼節點與已有節點具有相同的通信性能。而實際上無線傳感器網絡存在多種異構情況,例如XBeeS2與XBeeS2Pro射頻模塊均為ZigBee路由器的主要組成部分,其采用相同的協議棧,彼此之間可通信并組建網絡。然而XBeeS2射頻功率僅為2 mW,室外通信距離為120 m,XBeeS2Pro射頻功率為63 mW,室外通信距離長達3 200 m,其價格是XBeeS2的3倍以上。文獻[4]將網絡節點的通信性能進行區分,在網絡中加入中繼節點使網絡連通,并通過減少后加入的中繼節點數量降低網絡能耗以節省網絡成本。文獻[21-22]研究由中繼節點和傳感器節點組成的異構網絡,在該網絡中加入新中繼節點,從而由負載平衡和能量有效等方面優化網絡性能。無線傳感器網絡中異構與同構的最大區別在于傳感器節點之間的通信性能[23],因此同種算法在這2種網絡中有明顯差異,且相關算法都需運用到圖增量?？紤]到同構場景的局限性,本文針對異構場景下的節點部署問題展開研究。

2 網絡模型與問題描述

文獻[4]將sensor節點按照通信性能進行區分:普通sensor節點為低性能節點,命名為S1;將高通信性能的sensor節點命名為S2,且S2的通信半徑大于S1,即RS2>RS1。2個節點之間通信半徑由其中通信半徑小的節點決定,如圖1所示(dist(S1,S2)代表S1和S2之間的歐式距離,三角形和圓形代表通信半徑不同的傳感器節點)。

圖1 2個節點之間的通信半徑示意圖
Fig.1 Schematic diagram of communication radius between
two nodes

根據上述對不同節點通信半徑的分析,本文在WSNs中部署中繼節點(WSN-RELAY)以實現網絡連通性,并對其進行形式化定義。

定義1在二維平面里,給定無向圖G=,V由S1和S2節點的集合SS1、SS2組成,且這2個集合互不相交。Srelay為中繼節點集合,是整個算法的輸出。邊集E中所有邊的2個頂點均滿足上述通信半徑的約束,表示為:

E={e(i,j) | dist(i,j)≤RS2,i∈SS1& &j∈SS2}∪

{e(i,j) | dist(i,j)≤RS1,i∈SS1‖j∈SS2}

(1)

新添加的邊和節點構成G=。將一定數量的中繼節點部署在滿足如上約束的無向圖G中,求得Srelay并使|Srelay|達到最小。WSN-RELAY與文獻[3]提出的STP-MSPBEL類似,且當RS1=RS2時,等價于STP-MSPBEL。由文獻[3]中最小斯坦納生成樹問題的證明可知,本文所研究的問題為NP難問題,即研究如何部署節點使得Srelay的中繼節點數量最小。解決該問題的方法包括傳統GA-RD算法及由其改進的IWGA-RD算法,本文在IWGA-RD算法的基礎上對節點優先級篩選方式進行優化。

1)GA-RD算法

GA-RD算法的主要思想是通過向森林T加入n-1個邊使T變成1棵樹,從而實現整個網絡的連通[4]。輸入G=,先求出在未加入中繼節點情況下已連通的邊集E,初始化空的森林T,在保證不出現環的情況下從E挑選邊加入T中,令E′=V×V-E,將其中的邊按邊長升序得到隊列Q,再將Q中的邊在不出現環的情況下加入T中,并加入中繼節點使網絡連通[15]。

2)IWGA-RD算法

IWGA-RD算法是先計算出各邊的權重,并將其按升序排列形成隊列Q。與GA-RD算法類似,IWGA-RD算法采用最小生成樹算法求解圖增量問題,再將Q中的元素利用迭代法依次加入森林T中,在e(i,j)為0的邊加入中繼節點使網絡連通,最后去掉多余的中繼節點。

以下介紹本文所提LWGA算法中邊的權重計算方法。由于S1與S2的通信性能不同,在2個sensor節點之間加入中繼節點時,會考慮到該因素。假設S2的通信性能與中繼節點近似,則權重的計算存在以下3種情況:

1)當2個sensor節點(設為i,j)均為S1時,所需中繼節點數量與2個節點之間的距離dist(i,j)和S1的通信半徑RS1有關。當dist(i,j)≤RS1時,i與j均在對方的通信范圍內,無需加入中繼節點,網絡本身為連通狀態;當dist(i,j)在RS1和2RS1之間時(見圖2),需加入1個中繼節點,該中繼節點同時在2個節點的通信范圍內,使得網絡連通;當dist(i,j)>2RS1時(見圖3),在2個sensor節點各自通信范圍的最遠處(2個節點通信范圍以外)分別加入1個中繼節點,計算該距離為dist(i,j)-2RS1,在此距離范圍內需部署中繼節點使得網絡連通,2個節點之間的權重計算公式如式(2)所示。

圖2 dist(i,j)∈(RS1,2RS1)示意圖Fig.2 Schematic diagram of dist(i,j)∈(RS1,2RS1)

圖3 dist(i,j)∈(2RS1,+∞)示意圖 Fig.3 Schematic diagram of dist(i,j)∈(2RS1,+∞)

(2)

2)當2個sensor節點分別為S1和S2時,在S1通信范圍最遠處部署1個中繼節點,將該中繼節點視為S2,其余節點的部署與2個S2節點之間的距離有關(見圖4),2個節點之間的權重計算公式如式(3)所示。

圖4 2節點分別為S1和S2時權重分布示意圖Fig.4 Schematic diagram of weight distribution whenthe two nodes are S1 and S2 respectively

(3)

3)當2個sensor節點均為S2時,其通信性能與加入的中繼節點接近,其約束半徑均為RS2,2個節點之間需部署的中繼節點數量僅與其間隔的距離有關,2個節點之間的權重計算公式如式(4)所示。

(4)

2個節點之間的權重w(e(i,j))與這2個節點之間連通所需的中繼節點數量有關,根據以上3種情況,可得出定義2。

定義2假設i、j均為sensor節點,SS1為S1節點的集合,SS2為S2節點的集合。當i,j∈SS1時,2個節點之間的權重如式(2)所示;當i∈SS1、j∈SS2時,2個節點之間的權重如式(3)所示;當i,j∈SS2時,2個節點之間的權重如式(4)所示。

3 算法描述

根據上述權重計算方法,本文對傳統IWGA-RD算法進行改進,提出一種基于權重及邊長的LWGA算法。

算法1LWGA算法

輸入圖G=

輸出Srelay(中繼節點集合)

1.設n=|V|且E’=V×V-E

2.定義1個空的森林T

3.計算各邊權重和邊長,并初始化1個權重和邊長升序(按權重排序,若權重相同,則按邊長排序)的隊列Q,其包含E’中所有元素

4.WHILE T中包含少于n-1個邊,DO

5.IF邊集E不等于空集

6.取E中任意元素e(i,j),并將其從E中清除

7.IF T中加元素e(i,j)后未出現回路

8.在T中加入元素e(i,j)

9.ELSE

10.取Q(Q中元素為升序排列)中第1個元素e(i,j),將其從Q中清除

11.IF T中加入元素e(i,j)后未出現回路且w(e(i,j))和dist(i,j)均不為零

12.將e(i,j)加入T,并在i、j之間部署中繼節點

13.END DO

LWGA算法先通過式(1)～式(3)計算出G中各邊的權重,再按權重升序排序,并將權重相同的邊按邊長升序排序,得到最終排序。LWGA算法的第11行中采用最小生成樹算法求解權重圖增量問題,然后找出Q中最小權重和邊長的邊加入森林T,若待加入邊的權重或邊長大于零,則表示該邊需加入中繼節點使其連通。

定理1LWGA算法在[0,w(Ek+1)]區間收斂。

證明LWGA算法在[0,w(Ek+1)]區間收斂證明如下:

w(e(i,j))+w(e(r,j))

(5)

當部署第k+1個節點時,對應的最小權重及邊長生成樹為LWT(Ik+1,Ek+1)。連通Ik+1的1棵樹為Ek+e(i,r)+e(r,j)-e(i,j),則有:

w(e(r,j))

(6)

由上述可知,每部署1個中繼節點,LWT上的權重之和就減1,當部署k個中繼節點時,LWT(Ik,Ek)的權重必然為定值,因此,LWGA算法在[0,w(Ek+1)]區間收斂,證畢。

設klwga=|Srelay|、kiwga=|Slwga|,在未部署節點前存在∑w(I0)=kiwga,其中,kiwga為采用IWGA-RD算法得到的中繼節點數量。與IWGA-RD算法相比,由于LWGA算法在權重相同的情況下按邊長依次升序排列,在增加節點時多了1個更優的篩選條件,因此其每部署1個新中繼節點,在生成樹邊長相同的情況下權重之和就比IWGA-RD算法減少1,最終所得權重之和∑w(In)必然小于kiwga,由此可知LWGA算法部署的中繼節點數量不超過IWGA-RD算法,從而得出結論:LWGA算法的近似解小于IWGA-RD算法,即klwga≤kiwga,說明采用LWGA算法部署的中繼節點更少。

4 實驗結果與分析

為驗證采用LWGA算法部署傳感器網絡時所需中繼節點數量的情況,本文使用MATLAB軟件進行仿真實驗。將低通信性能節點S1的半徑RS1固定為30 m,可變參數為低通信性能節點S1的數量(NS1)、高通信性能節點S2的數量(NS2)及半徑。圖5為某次部署節點前后的節點隨機拓撲情況,區域中已有方形節點為隨機部署。圖5(a)為部署節點前的節點隨機拓撲情況(有10個高性能節點、100個低性能節點),其中節點位置、節點之間是否連通均為隨機;圖5(b)為部署節點后的節點隨機拓撲情況,圓形節點為后加入的中繼節點。

圖5 部署節點前后的節點隨機拓撲情況Fig.5 Random topology of nodes before andafter node deployment

4.1 小規模仿真實驗

以300 m×300 m正方形區域作為實驗區域,通過調整可變參數大小,觀測所需中繼節點的數量,取100次隨機觀測結果的平均值作為實驗結果,并將LWGA算法得到的結果與GA-RD、IWGA-RD算法進行對比,實驗參數設置如表1所示,其中“—”代表自變量。

表1 小規模仿真實驗參數設置Table 1 Parameter setting of small scale simulationexperiment

在實驗區域隨機部署100個低通信性能節點S1及10個高通信性能節點S2,在改變S2通信半徑RS2的情況下,對比GA-RD、IWGA-RD及LWGA算法所需中繼節點的數量,結果如圖6所示(1號實驗)?？梢钥闯?當RS2為30 m時,GA-RD算法與IWGA-RD算法所需中繼節點數量相同,LWGA算法所需中繼節點數量最少;當RS2為30 m～50 m時,GA-RD算法所需中繼節點數量略有下降,LWGA算法和IWGA-RD算法所需中繼節點數量降幅明顯;當RS2大于50 m時,GA-RD算法所需中繼節點數量幾乎不變,LWGA算法和IWGA-RD算法所需中繼節點數量保持下降;當RS2為50 m～130 m時,IWGA-RD算法所需中繼節點數量較GA-RD算法減少約25%,而LWGA算法所需中繼節點數量較IWGA-RD算法減少約30%,故LWGA算法的性能優于另外2種算法;當RS2大于90 m時,IWGA-RD、LWGA與GA-RD算法所需中繼節點數量保持上述趨勢且差距更明顯。

圖6 S2通信半徑與中繼節點數量關系曲線1Fig.6 Relationship curve 1 between the communicationradius of S2 and the number of relay nodes

在實驗區域部署150個低通信性能節點S1,將高通信性能節點S2半徑設置為60 m,在改變S2數量的情況下,對比GA-RD、IWGA-RD及LWGA算法在解決WSN-RELAY問題時所需中繼節點的數量,結果如圖7所示(2號實驗)。可以看出:當S2數量小于5時,GA-RD、IWGA-RD算法所需中繼節點數量接近,LWGA算法較這2種算法所需中繼節點數量減少約25%;當S2數量大于5時,GA-RD算法所需中繼節點數量先不變再下降,IWGA-RD、LWGA算法所需中繼節點數量均逐漸減少,且LWGA算法所需中繼節點數量較IWGA-RD算法減少約30%;當S2數量為20～25時,LWGA算法所需中繼節點數量仍低于IWGA-RD算法且趨于恒定。因此,當S2數量為0～25時,LWGA算法所需中繼節點數量較GA-RD、IWGA-RD算法更少,LWGA算法性能更優。

圖7 S2數量與中繼節點數量關系曲線1Fig.7 Relationship curve 1 between the number ofS2 and relay nodes

在實驗區域部署10個高通信性能節點S2,將中繼節點和S2的通信半徑RS2設置為60 m,通過改變低性能節點S1的數量,觀測GA-RD、IWGA-RD及LWGA算法在解決WSN-RELAY問題時所需中繼節點的數量,結果如圖8所示(3號實驗)?？梢钥闯?當S1數量為80時,3種算法所需中繼節點數量大致相同;隨著S1數量的增加,3種算法所需中繼節點數量均出現下降,IWGA-RD算法所需中繼節點數量較GA-RD算法減少約10%,LWGA算法所需中繼節點數量較IWGA-RD算法減少約20%;當S1數量為180時,3種算法所需中繼節點數量幾乎相同。因此,當S1數量為80～180時,LWGA算法較GA-RD、IWGA-RD算法性能更優。

圖8 S1數量與中繼節點數量關系曲線1Fig.8 Relationship curve 1 between the number ofS1 and relay nodes

4.2 大規模仿真實驗

以1 000 m×1 000 m正方形區域作為實驗區域,通過調整可變參數大小,觀測所需中繼節點的數量,取100次隨機觀測結果的平均值作為實驗結果,并將LWGA算法得到的結果與GA-RD、IWGA-RD算法進行對比,實驗參數設置如表2所示,其中“—”代表自變量。

表2 大規模仿真實驗參數設置Table 2 Parameter setting of big scale simulationexperiment

在實驗區域隨機部署200個低通信性能節點S1及20個高通信性能節點S2,由于中繼節點半徑僅為實驗區域邊長的6%,因此大規模實驗環境下需部署更多中繼節點。在改變S2通信半徑RS2的情況下,對比GA-RD、IWGA-RD及LWGA算法所需中繼節點的數量,結果如圖9所示(4號實驗)?？梢钥闯?當RS2不斷增加時,3種算法所需中繼節點數量均出現下降;當RS2為60 m～120 m時,3種算法所需中繼節點數量降幅較大;當RS2大于120 m時,3種算法所需中繼節點數量降幅趨于平緩;當RS2相同時,IWGA-RD算法所需中繼節點數量較GA-RD算法減少約10%,LWGA算法所需中繼節點數量較IWGA-RD算法減少約10%。因此,LWGA算法性能要優于IWGA-RD、GA-RD算法。

圖9 S2通信半徑與中繼節點數量關系曲線2Fig.9 Relationship curve 2 between the communicationradius of S2 and the number of relay nodes

在實驗區域部署200個低通信性能節點S1,將高通信性能節點S2半徑設置為60 m,在改變S2數量的情況下,對比GA-RD、IWGA-RD及LWGA算法在解決WSN-RELAY問題時所需中繼節點的數量,結果如圖10所示(5號實驗)?？梢钥闯?隨著S2數量的增加,3種算法所需中繼節點數量都出現下降且降幅較小;當S2數量達到60時,IWGA-RD、LWGA算法所需中繼節點數量接近;當S2數量為20～60時,IWGA-RD算法所需中繼節點數量較GA-RD算法減少約15%,LWGA算法所需中繼節點數量較IWGA-RD算法減少約10%。

圖10 S2數量與中繼節點數量關系曲線2Fig.10 Relationship curve 2 between the number ofS2 and relay nodes

在實驗區域部署20個高通信性能節點S2,將中繼節點和S2的通信半徑RS2設置為60 m,通過改變低性能節點S1的數量,觀測GA-RD、IWGA-RD及LWGA算法在解決WSN-RELAY問題時所需中繼節點的數量,結果如圖11所示(6號實驗)。可以看出:隨著S1數量增加,3種算法所需中繼節點數量出現遞增,IWGA-RD算法所需中繼節點數量較GA-RD算法減少5%～10%,LWGA算法所需節點數量較IWGA-RD算法減少5%～10%,LWGA算法性能最優。由于節點半徑與實驗區域邊長相差較大,因此造成上述實驗結果與小規模環境下的變化規律有差異。

圖11 S1數量與中繼節點數量關系曲線2Fig.11 Relationship curve 2 between the number ofS1 and relay nodes

4.3 假設檢驗與實驗結論

4.3.1 假設檢驗

由于IWGA-RD算法基于GA-RD算法改進得到,因此只需驗證LWGA算法優于IWGA-RD算法,即可得證其優于GA-RD算法。為從統計學角度更好地說明LWGA算法的優異性能,以下通過假設檢驗[24]來驗證LWGA算法與IWGA-RD算法之間的顯著差異,從而證明本文實驗結果的可靠性。

設H0表示LWGA算法與IWGA-RD算法在不同條件下所需中繼節點數量無顯著差異,H1表示LWGA算法與IWGA-RD算法在不同條件下所需中繼節點數量有顯著差異(H0:原假設,H1:備擇假設)。將統計量設置為不同條件下IWGA-RD、LWGA算法再次分別進行100次隨機實驗所需中繼節點數量,顯著水平α設置為0.05,實驗樣本出現的概率記為p。假設檢驗的原理是根據實驗樣本統計量的大小及其分布確定檢驗假設成立可能性概率p的大小并進行判斷:若p>α,說明α所取水準不顯著,在H0條件下出現的數據樣本不是小概率事件,H0假設正確,則拒絕H1假設,接受H0假設,即認為差別很可能是由抽樣誤差造成的,在統計上不成立；若p≤α,說明所取α水準顯著,在H0條件下出現的數據樣本是小概率事件,H0假設錯誤,則拒絕H0假設,接受H1假設,即認為此差別很可能是實驗因素不同造成的,故在統計上成立。表3～表5為表1、表2中6組實驗經假設檢驗所得p值。由表3可知,6組實驗的p值均滿足p<α,因此設立的備擇假設H1成立,即:LWGA算法與IWGA-RD算法所需中繼節點數量有顯著差異,因此本文實驗樣本結果具有可靠性,在統計上成立。

表3 不同S2通信半徑下實驗1和實驗4的p值Table 3 p values of Experiment 1 and Experiment 4under different communication radius of S2

表4 不同S2數量下實驗2和實驗5的p值Table 4 p values of Experiment 2 and Experiment 5under different numbers of S2

表5 不同S1數量下實驗3和實驗6的p值Table 5 p values of Experiment 3 and Experiment 6under different numbers of S1

4.3.2 實驗結論

由上述實驗結果可知,在相同的實驗場景下,與GA-RD、IWGA-RD算法相比,LWGA算法可減少所需中繼節點的數量,能有效降低網絡負載與部署成本,具有更好的網絡性能。由實驗結果分析可知,在某些條件固定的情況下,LWGA算法在自變量改變的部分區間內呈現出一定優勢,但超過臨界值后,3種算法的性能接近。根據文獻[25]對節點負載數據的相關分析,當自變量為節點數量時,在實驗區域內部署節點數量越大,各節點承擔的數據包越多,當低性能節點數量增加時,整個網絡負載隨之升高,因此3種算法性能在某些條件下近似。當改變性能節點通信半徑和高性能節點數量后,3種算法的實驗結果差異趨于明顯,這是因為高通信性能節點的通信半徑與中繼節點接近,是低性能節點通信半徑的2倍甚至更多,改變其相關參數對整個網絡影響較大,因此LWGA算法在節省中繼節點數量上的效果也更顯著。綜上所述,LWGA算法優于GA-RD、IWGA-RD算法,可得到更好的網絡性能。

5 結束語

為了用盡量少的中繼節點解決WSNs網絡擁塞問題,本文提出一種基于權重及邊長的中繼節點部署LWGA算法,在IWGA-RD算法的基礎上按節點權重和邊長對邊進行排序,設定節點優先級依次迭代加入中繼節點,以減少相同環境下部署中繼節點的數量。仿真實驗與假設檢驗結果表明,該算法較GA-RD、IWGA-RD算法所需中繼節點更少,具有更好的網絡性能。后續將用盡量少的中繼節點實現網絡負載平衡,以解決無線傳感器網絡耗能不均勻的問題。