馬千里,袁 易,申朝暉

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

0 概述

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

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

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

1 研究現(xiàn)狀

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

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

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

2 網(wǎng)絡模型與問題描述

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

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

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

定義1在二維平面里,給定無向圖G=,V由S1和S2節(jié)點的集合SS1、SS2組成,且這2個集合互不相交。Srelay為中繼節(jié)點集合,是整個算法的輸出。邊集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)

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

1)GA-RD算法

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

2)IWGA-RD算法

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

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

1)當2個sensor節(jié)點(設為i,j)均為S1時,所需中繼節(jié)點數(shù)量與2個節(jié)點之間的距離dist(i,j)和S1的通信半徑RS1有關。當dist(i,j)≤RS1時,i與j均在對方的通信范圍內(nèi),無需加入中繼節(jié)點,網(wǎng)絡本身為連通狀態(tài);當dist(i,j)在RS1和2RS1之間時(見圖2),需加入1個中繼節(jié)點,該中繼節(jié)點同時在2個節(jié)點的通信范圍內(nèi),使得網(wǎng)絡連通;當dist(i,j)>2RS1時(見圖3),在2個sensor節(jié)點各自通信范圍的最遠處(2個節(jié)點通信范圍以外)分別加入1個中繼節(jié)點,計算該距離為dist(i,j)-2RS1,在此距離范圍內(nèi)需部署中繼節(jié)點使得網(wǎng)絡連通,2個節(jié)點之間的權重計算公式如式(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節(jié)點分別為S1和S2時,在S1通信范圍最遠處部署1個中繼節(jié)點,將該中繼節(jié)點視為S2,其余節(jié)點的部署與2個S2節(jié)點之間的距離有關(見圖4),2個節(jié)點之間的權重計算公式如式(3)所示。

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

(3)

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

(4)

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

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

3 算法描述

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

算法1LWGA算法

輸入圖G=

輸出Srelay(中繼節(jié)點集合)

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)后未出現(xiàn)回路

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

9.ELSE

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

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

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

13.END DO

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

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

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

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

(5)

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

w(e(r,j))

(6)

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

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

4 實驗結果與分析

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

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

4.1 小規(guī)模仿真實驗

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

表1 小規(guī)模仿真實驗參數(shù)設置Table 1 Parameter setting of small scale simulationexperiment

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

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

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

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

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

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

4.2 大規(guī)模仿真實驗

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

表2 大規(guī)模仿真實驗參數(shù)設置Table 2 Parameter setting of big scale simulationexperiment

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

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

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

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

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

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

4.3 假設檢驗與實驗結論

4.3.1 假設檢驗

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

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

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

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

表5 不同S1數(shù)量下實驗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算法可減少所需中繼節(jié)點的數(shù)量,能有效降低網(wǎng)絡負載與部署成本,具有更好的網(wǎng)絡性能。由實驗結果分析可知,在某些條件固定的情況下,LWGA算法在自變量改變的部分區(qū)間內(nèi)呈現(xiàn)出一定優(yōu)勢,但超過臨界值后,3種算法的性能接近。根據(jù)文獻[25]對節(jié)點負載數(shù)據(jù)的相關分析,當自變量為節(jié)點數(shù)量時,在實驗區(qū)域內(nèi)部署節(jié)點數(shù)量越大,各節(jié)點承擔的數(shù)據(jù)包越多,當?shù)托阅芄?jié)點數(shù)量增加時,整個網(wǎng)絡負載隨之升高,因此3種算法性能在某些條件下近似。當改變性能節(jié)點通信半徑和高性能節(jié)點數(shù)量后,3種算法的實驗結果差異趨于明顯,這是因為高通信性能節(jié)點的通信半徑與中繼節(jié)點接近,是低性能節(jié)點通信半徑的2倍甚至更多,改變其相關參數(shù)對整個網(wǎng)絡影響較大,因此LWGA算法在節(jié)省中繼節(jié)點數(shù)量上的效果也更顯著。綜上所述,LWGA算法優(yōu)于GA-RD、IWGA-RD算法,可得到更好的網(wǎng)絡性能。

5 結束語

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