無線傳感執(zhí)行器網(wǎng)絡(luò)中多源容錯(cuò)拓?fù)淇刂扑惴ㄑ芯?

楊明霞,畢宏博,柴國飛

(衢州學(xué)院電氣與信息工程學(xué)院,衢州 324000)

無線傳感執(zhí)行器網(wǎng)絡(luò)中多源容錯(cuò)拓?fù)淇刂扑惴ㄑ芯?

楊明霞*,畢宏博,柴國飛

(衢州學(xué)院電氣與信息工程學(xué)院,衢州 324000)

拓?fù)淇刂剖茄娱L無線傳感器網(wǎng)絡(luò)生命時(shí)間的關(guān)鍵技術(shù)。針對(duì)異構(gòu)網(wǎng)絡(luò)的復(fù)雜性,提出了基于功率控制的分布式多源容錯(cuò)拓?fù)淇刂扑惴∕SFT。在由大量計(jì)算、能量受限的傳感器節(jié)點(diǎn)和少量性能較優(yōu)的執(zhí)行器節(jié)點(diǎn)組成的異構(gòu)無線傳感執(zhí)行器網(wǎng)絡(luò)模型中,算法保證任意傳感器節(jié)點(diǎn)與執(zhí)行器節(jié)點(diǎn)之間至少存在k條不相交路徑同時(shí)選擇權(quán)值較優(yōu)節(jié)點(diǎn)使路徑總功耗盡可能少,這樣當(dāng)任意k-1個(gè)節(jié)點(diǎn)失效時(shí)并不影響網(wǎng)絡(luò)的連通性。理論分析證明算法能以O(shè)(n)的時(shí)間和消息代價(jià)構(gòu)造網(wǎng)絡(luò)拓?fù)?仿真實(shí)驗(yàn)進(jìn)一步證實(shí)算法的有效性。

無線傳感執(zhí)行器網(wǎng)絡(luò);異構(gòu);容錯(cuò);拓?fù)淇刂?功率控制

無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)由大量價(jià)格低廉的微型傳感器節(jié)點(diǎn)自組織組成,廣泛應(yīng)用于對(duì)象跟蹤、環(huán)境監(jiān)測(cè)、災(zāi)害預(yù)防等領(lǐng)域[1]。節(jié)點(diǎn)的能量有限且通常不可重復(fù)補(bǔ)充,因此節(jié)能是無線傳感器網(wǎng)絡(luò)需要考慮的重要問題[2]。拓?fù)淇刂剖潜ＷC網(wǎng)絡(luò)連通、平衡節(jié)點(diǎn)能耗,增加運(yùn)行時(shí)間的高效可行技術(shù),它通常包括拓?fù)錁?gòu)建與拓?fù)渚S護(hù)兩個(gè)過程[3]。拓?fù)錁?gòu)建用于減少網(wǎng)絡(luò)鏈路以節(jié)約能量,當(dāng)節(jié)點(diǎn)失效或當(dāng)前拓?fù)湟呀?jīng)不再最優(yōu)時(shí)運(yùn)行拓?fù)渚S護(hù)重構(gòu)網(wǎng)絡(luò)。然而,重構(gòu)網(wǎng)絡(luò)需要消耗大量的能量,同時(shí)節(jié)點(diǎn)通常部署在戰(zhàn)場(chǎng)、森林等環(huán)境惡劣地區(qū),極易出現(xiàn)鏈路斷裂、硬件錯(cuò)誤等問題,因此構(gòu)造容錯(cuò)性好、可靠性高的拓?fù)湟呀?jīng)成為了關(guān)鍵[4]。另一方面當(dāng)前研究往往過于理想化,即假設(shè)各個(gè)傳感器節(jié)點(diǎn)的性能完全相同,與實(shí)際嚴(yán)重脫節(jié)。文獻(xiàn)[5]指出異構(gòu)WSNs可以分為計(jì)算異構(gòu)、鏈路異構(gòu)和能量異構(gòu),同時(shí)如果節(jié)點(diǎn)能夠部署合適的話,將極大改善網(wǎng)絡(luò)的收發(fā)速率并能將網(wǎng)絡(luò)運(yùn)行時(shí)間提升五倍,因此必須考慮節(jié)點(diǎn)的異構(gòu)。

為了研究異構(gòu)網(wǎng)絡(luò)的性能,近年來在WSNs基礎(chǔ)上引入若干執(zhí)行器節(jié)點(diǎn)衍生出了一種稱為無線傳感執(zhí)行器網(wǎng)絡(luò)[6](WSANs)的新型網(wǎng)絡(luò)模型。WSANs將網(wǎng)絡(luò)節(jié)點(diǎn)分為性能受限的傳感器節(jié)點(diǎn)(Sensor)和能量充足、具有較強(qiáng)計(jì)算和通信能力的執(zhí)行器節(jié)點(diǎn)(Actor)。Actor由于價(jià)格昂貴其數(shù)量通常遠(yuǎn)遠(yuǎn)小于Sensor。Sensor以多跳的方式將采集的數(shù)據(jù)向Actor發(fā)送。當(dāng)數(shù)據(jù)到達(dá)Actor后,Actor將Sensor采集的數(shù)據(jù)進(jìn)行融合后發(fā)向外部網(wǎng)絡(luò)。因此,可以將執(zhí)行器節(jié)點(diǎn)集當(dāng)成多個(gè)Sink節(jié)點(diǎn)部署在網(wǎng)絡(luò)中,將數(shù)據(jù)傳輸過程分為Sensor-Sensor,Sensor-Actor和Actor-Actor 3種不同層次,并最終發(fā)向外部網(wǎng)絡(luò)。Actor-Actor之間的鏈路由于由性能較高的節(jié)點(diǎn)組成因而較為穩(wěn)定,而Sensor-Sensor和Sensor-Actor則極易由于Sensor的失效而造成網(wǎng)絡(luò)的癱瘓。

本文在WSANs的基礎(chǔ)上研究容錯(cuò)拓?fù)淇刂扑惴?提出了MSFT(Multiple Source Fault-Tolerant Algorithm)用于保證網(wǎng)絡(luò)中任意Sensor節(jié)點(diǎn)至少存在k條到達(dá)Actor的不相交路徑,如果網(wǎng)絡(luò)是k連通的,那么任意k-1個(gè)節(jié)點(diǎn)的失效不會(huì)導(dǎo)致網(wǎng)絡(luò)中斷,同時(shí)提高了網(wǎng)絡(luò)的路由靈活性。

1 相關(guān)工作

拓?fù)淇刂扑惴ㄖ饕譃楣β士刂坪退哒{(diào)度兩種類型。睡眠調(diào)度[7-9]將網(wǎng)絡(luò)節(jié)點(diǎn)分為骨干節(jié)點(diǎn)和非骨干節(jié)點(diǎn),骨干節(jié)點(diǎn)一直處于活躍狀態(tài)并負(fù)責(zé)監(jiān)聽與轉(zhuǎn)發(fā)數(shù)據(jù),而非骨干節(jié)點(diǎn)只有在數(shù)據(jù)需要發(fā)送時(shí)才會(huì)蘇醒,其他時(shí)候處于休眠以節(jié)省能量。由于其不是本文主要研究內(nèi)容,在此不作詳細(xì)敘述。功率控制通過調(diào)節(jié)網(wǎng)絡(luò)節(jié)點(diǎn)的發(fā)送功率,在滿足網(wǎng)絡(luò)連通覆蓋度的前提下,均衡節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目,剔除節(jié)點(diǎn)間不必要的通信鏈路,形成一個(gè)數(shù)據(jù)轉(zhuǎn)發(fā)的優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu),達(dá)到優(yōu)化網(wǎng)絡(luò)生命時(shí)間的目的。當(dāng)前,已經(jīng)有很多學(xué)者對(duì)功率控制算法進(jìn)行研究。

LMA[10]是一種基于節(jié)點(diǎn)度的功率控制算法,初始時(shí)每個(gè)節(jié)點(diǎn)以相同功率廣播LifeMsg消息,鄰居節(jié)點(diǎn)收到消息后回復(fù)LifeAckMsg給發(fā)送方。發(fā)送方對(duì)收到的回復(fù)進(jìn)行統(tǒng)計(jì),如果其值在預(yù)先設(shè)定的最小與最大閾值之間則算法結(jié)束;否則,調(diào)整發(fā)送功率直到節(jié)點(diǎn)度到達(dá)閾值。LMN[11]是LMA的改進(jìn),在回復(fù)LifeAckMsg時(shí),將最新的鄰居節(jié)點(diǎn)數(shù)量添加到消息包,并通過計(jì)算自身的平均鄰域鄰居節(jié)點(diǎn)數(shù)判斷是否在閾值范圍內(nèi)。這類算法利用局部信息能夠達(dá)到一定程度的優(yōu)化,但是依賴于初始閾值的設(shè)定,同時(shí)難以保證網(wǎng)絡(luò)的全連通。NNPC[11]采用了近鄰算法評(píng)估網(wǎng)絡(luò)節(jié)點(diǎn)的密度并計(jì)算相應(yīng)的最優(yōu)發(fā)送功率,擺脫了初始閾值的約束,節(jié)點(diǎn)根據(jù)最優(yōu)發(fā)送功率發(fā)送數(shù)據(jù)并提高了網(wǎng)絡(luò)生命時(shí)間。但是,該算法需要保存網(wǎng)絡(luò)的全局拓?fù)湫畔?因此是一種集中式算法而且只適用于較小規(guī)模的網(wǎng)絡(luò)。

文獻(xiàn)[12]指出物理層、MAC層及網(wǎng)絡(luò)層之間存在相互影響、相互制約的關(guān)系。物理層的發(fā)射功率和傳輸速率影響了MAC層的接入控制和網(wǎng)絡(luò)層的路由選擇;MAC層限制了信源的帶寬和分組延遲,從而影響了網(wǎng)絡(luò)層的路由選擇。因此,將期望節(jié)點(diǎn)度、連通因子和干擾競(jìng)爭(zhēng)節(jié)點(diǎn)數(shù)等信息進(jìn)行融合,建立了博弈模型并提出一種能耗均衡的可靠拓?fù)洳┺乃惴‥BRGA。算法分為鄰居節(jié)點(diǎn)發(fā)現(xiàn)、博弈執(zhí)行和功率確定3個(gè)階段。在鄰居節(jié)點(diǎn)發(fā)現(xiàn)階段,各個(gè)節(jié)點(diǎn)通過信息交換建立鄰居節(jié)點(diǎn)列表,并在博弈執(zhí)行過程中通過該列表比較節(jié)點(diǎn)信息選擇不同發(fā)射功率對(duì)網(wǎng)絡(luò)狀況造成的影響,并最終在功率確定階段確定最大化自身收益的發(fā)射功率。算法能夠保證網(wǎng)絡(luò)的連通,但是沒有考慮到節(jié)點(diǎn)剩余能量對(duì)發(fā)送功率產(chǎn)生的影響,如果節(jié)點(diǎn)剩余能量較低同時(shí)又具有較大的傳輸半徑,那么網(wǎng)絡(luò)可能會(huì)由于部分節(jié)點(diǎn)的能量耗盡而提前死亡[13]。同時(shí),博弈過程的時(shí)間因素也是一個(gè)值得考慮的問題。

文獻(xiàn)[19]面向異構(gòu)網(wǎng)絡(luò),基于反向連通支配集樹,研究一種低信息復(fù)雜度的分布式拓?fù)錁?gòu)建算法?；谧钚∵B通支配集進(jìn)行虛擬骨干的構(gòu)建,從而優(yōu)化連通支配集的規(guī)模和通信功耗,在保證連通性的同時(shí)關(guān)閉網(wǎng)絡(luò)冗余節(jié)點(diǎn)以降低能耗。文獻(xiàn)[20]提出一種面向節(jié)能和容錯(cuò)的分布式拓?fù)淇刂扑惴?在連通支配集建立后,選擇容錯(cuò)度大的節(jié)點(diǎn)作為備份節(jié)點(diǎn),在數(shù)據(jù)收集過程中對(duì)支配節(jié)點(diǎn)的能耗進(jìn)行均衡。

2 模型與問題描述

2.1 網(wǎng)絡(luò)模型

無線傳感執(zhí)行器網(wǎng)絡(luò)由M個(gè)執(zhí)行器節(jié)點(diǎn)和N個(gè)傳感器節(jié)點(diǎn)組成,Actor靜止均勻分布在L×L的正方形區(qū)域內(nèi),它們負(fù)責(zé)將收到的傳感器節(jié)點(diǎn)數(shù)據(jù)發(fā)送到外部網(wǎng)絡(luò),Sensor則在區(qū)域內(nèi)隨機(jī)進(jìn)行部署。假設(shè)Sensor的能量和通信半徑異構(gòu)并且有限,Actor的能量可以無限大。本文中僅僅考慮Sensor-Sensor和Sensor-Actor之間的通信,而忽略Actor將采集的數(shù)據(jù)發(fā)向外部網(wǎng)絡(luò)的過程。用G=(V,E)表示該網(wǎng)絡(luò)模型,其中V表示圖中的節(jié)點(diǎn),由v1,v2,…,vN,vN+1,vN+2,…,vN+M組成。其中,前N個(gè)節(jié)點(diǎn)表示傳感器節(jié)點(diǎn)集而后面M個(gè)節(jié)點(diǎn)表示執(zhí)行器節(jié)點(diǎn)。E是圖G中節(jié)點(diǎn)V組成的鏈路集合。各個(gè)節(jié)點(diǎn)具有唯一的ID,節(jié)點(diǎn)之間通過信息交換獲得一跳范圍內(nèi)的鄰居信息而無須配置GPS等定位裝置以獲取地理位置。

2.2 問題描述

為了更好地描述本文研究的問題,首先給出以下定義:

定義1不相交路徑

假設(shè)節(jié)點(diǎn)u和v之間的任意兩條路徑分別為p1=(u,w11,w12,…,w1m,v)和p2=(u,w21,w22,…,w2n,v),如果鏈路p1和p2中的節(jié)點(diǎn)除了首尾的端點(diǎn)u和v外,其他中間節(jié)點(diǎn)均不相同,則稱p1和p2是兩條不相交的鏈路。

定義2k連通網(wǎng)絡(luò)

無線傳感器網(wǎng)絡(luò)是k連通的當(dāng)且僅當(dāng)網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)均存在k條通向執(zhí)行器節(jié)點(diǎn)的不相交路徑。

定義3節(jié)點(diǎn)的初始功率設(shè)定

節(jié)點(diǎn)剩余能量充足時(shí)可覆蓋的范圍較大,當(dāng)剩余能量較少時(shí),為了避免能量消耗過快,節(jié)點(diǎn)需要減小功率以縮小傳輸范圍,當(dāng)功率減少到最低發(fā)射功率時(shí)則不再改變。初始時(shí),ni的剩余能量為E(ni),定義式(1)作為節(jié)點(diǎn)ni的初始功率,其中Pmax,Pmin,Emax,Emin分別表示節(jié)點(diǎn)的最大、最小可調(diào)功率和最大、最小能量。

(1)

定義4節(jié)點(diǎn)之間的傳輸功率

本文采用式(2)的計(jì)算傳輸功率,假設(shè)任意節(jié)點(diǎn)ni和nj之間的距離為dis(ni,nj),則ni和nj之間進(jìn)行通信需要的最小功率為P(ni,nj)。ni和nj能夠通信當(dāng)且僅當(dāng)ni和nj的各自傳輸功率P(ni)和P(nj)均大于P(ni,nj)。

P(ni,nj)=dis(ni,nj)α

(2)

定義5通信鏈路權(quán)值

消息傳輸失敗的概率隨著傳輸距離的增加而不斷變大,同時(shí)傳輸距離的增加將導(dǎo)致節(jié)點(diǎn)消耗的功率增大。另一方面,如果傳輸鏈路中存在能量水平較低的節(jié)點(diǎn),那么網(wǎng)絡(luò)可能會(huì)由于個(gè)別節(jié)點(diǎn)的能量耗盡而提前死亡。本文定義式(3)～(6)用于衡量通信鏈路優(yōu)劣,其中Emin(ni,mj)和Pmax(ni,nj)分別表示當(dāng)前路徑(ni,ni+1,ni+2,…,ni+p,mj)中所有路徑中間節(jié)點(diǎn)的最小能量和相鄰節(jié)點(diǎn)一跳路徑中功耗最大值。當(dāng)鏈路的權(quán)值相等時(shí)比較一跳路徑中需要的功耗最大值Pmax,如果還相等則比較ID。

Emin(ni,mj)=min{E(nk)},nk∈[ni,ni+1,…,ni+p]

(3)

Pmax(ni,mj)=max{P(nk,nk+1)},
k∈[i,i+1,…,i+p]

(4)

(5)

(6)

定義6k-ATC問題

本文研究無線傳感執(zhí)行器網(wǎng)絡(luò)的k連接問題,同時(shí)使得優(yōu)化后的網(wǎng)絡(luò)拓?fù)滏溌房偣β首钚　＜僭O(shè)網(wǎng)絡(luò)由傳感器節(jié)點(diǎn)N={v1,v2,…,vN}和執(zhí)行器節(jié)點(diǎn)M={vN+1,vN+2,…,vN+M}組成且N∩M=Φ。對(duì)于網(wǎng)絡(luò)中任意節(jié)點(diǎn)v∈V都至少存在k條能夠到達(dá)執(zhí)行器節(jié)點(diǎn)集合M的不相交路徑,同時(shí)使得這些路徑的通信鏈路權(quán)值之和最小。定義目標(biāo)函數(shù)為:

(7)

3 MSFT算法描述

MSFT算法從各個(gè)執(zhí)行器節(jié)點(diǎn)以最大功率廣播PathInfo(ID,hops)消息開始,其中hops主要用于控制執(zhí)行器節(jié)點(diǎn)的可覆蓋范圍,傳感器節(jié)點(diǎn)每收到一次信息需要將對(duì)應(yīng)的hops減1,hops越大表示信息被轉(zhuǎn)發(fā)的次數(shù)越多,當(dāng)hops等于0時(shí)信息停止轉(zhuǎn)發(fā);一跳鄰域的鄰居節(jié)點(diǎn)u收到消息后,通過信號(hào)強(qiáng)度RSSI估計(jì)與執(zhí)行器節(jié)點(diǎn)m之間的距離并計(jì)算通信需要消耗的功率,然后在本地保存一個(gè)列表PathList(Path(m,u),E(u),P(m,u),Pmax,W(v,m)),其中向量Path(m,u)用于保存u與執(zhí)行器節(jié)點(diǎn)之間的路徑,E(u)表示當(dāng)前鏈路中所有節(jié)點(diǎn)的最小能量,P(m,u),Pmax分別表示當(dāng)前鏈路總功耗和單跳最大功耗,W(v,m)表示鏈路權(quán)值。一般來說此時(shí)節(jié)點(diǎn)只有一條可達(dá)執(zhí)行器節(jié)點(diǎn)的路徑,因此需要向鄰域轉(zhuǎn)發(fā)PathInfo(Path(m,u),E(u),P(m,u),Pmax,hops)并啟動(dòng)一個(gè)定時(shí)器timer以搜集其他路徑集合。

在超時(shí)時(shí)間中,節(jié)點(diǎn)收到消息后按照之前方法計(jì)算與發(fā)送者u之間通信需要消耗的功率P(u,v),同時(shí)對(duì)信息包進(jìn)行解析,更新路徑為Path(m,u,v)并累加總功耗P(v,m)=P(u,v)+P(u,m),接著將節(jié)點(diǎn)能量與鏈路最小能量Emin進(jìn)行比較,如果當(dāng)前節(jié)點(diǎn)能量小于Emin則更新最小能量并計(jì)算路徑權(quán)值W(m,v),然后存儲(chǔ)到列表PathList中。

超時(shí)結(jié)束后,當(dāng)前節(jié)點(diǎn)對(duì)PathList列表中存儲(chǔ)的路徑按照權(quán)值大小進(jìn)行排序,記為NPathList。為了保證網(wǎng)絡(luò)的容錯(cuò)性,需要確保k條到達(dá)執(zhí)行器節(jié)點(diǎn)的連通路徑并將該路徑集合記為K-Connective-Path。初始時(shí)K-Connective-Path為空,將NPathList中權(quán)值最小的路徑添加到K-Connective-Path中并將其從NPathList中刪除,然后對(duì)NPathList開始進(jìn)行遍歷。如果當(dāng)前路徑Path(m,w1,w2,…,v)與K-Connective-Path中的路徑不相交,則將其從NPathList刪除并添加到K-Connective-Path列表中;否則,在NPathList中刪除該路徑并繼續(xù)遍歷下一條記錄。在判斷不相交路徑的過程中,假設(shè)當(dāng)前比較的NPathList和K-Connective-Path列表路徑記錄分別為pn(m,wn1,wn2,…,v)和pk(m,wk1,wk2,…,v),首先分別對(duì)路徑pn和pk中節(jié)點(diǎn)按照ID進(jìn)行排序,然后用兩個(gè)指針分別指向排序后的路徑列表進(jìn)行遍歷,如果路徑中存在除自身節(jié)點(diǎn)或執(zhí)行器節(jié)點(diǎn)之外其他ID相等的節(jié)點(diǎn),則證明兩條路徑相交,否則將pn添加到列表中。

以上過程不斷重復(fù)直到當(dāng)前K-Connective-Path列表已經(jīng)存在k條路徑或循環(huán)正常結(jié)束。節(jié)點(diǎn)向外廣播一個(gè)PathInfo(Path(m,vk),Emin,P(m,vk),Pmax)信息,消息中存儲(chǔ)的分別是列表中當(dāng)前存在的可達(dá)路徑、對(duì)應(yīng)路徑中的最小能量集合以及功耗列表信息。如果當(dāng)前K-Connective-Path列表中的記錄數(shù)小于k,則說明當(dāng)前距離執(zhí)行器節(jié)點(diǎn)m最小跳數(shù)的有效路徑少于k,則節(jié)點(diǎn)需要繼續(xù)等待其他節(jié)點(diǎn)(跳數(shù)略大)的廣播信息直到路徑數(shù)達(dá)到k。

當(dāng)網(wǎng)絡(luò)中所有節(jié)點(diǎn)均已存儲(chǔ)了k條可達(dá)路徑,則算法開始第2階段的標(biāo)記工作。節(jié)點(diǎn)u根據(jù)本地K-Connective-Path列表中存儲(chǔ)的路徑獲得k條可達(dá)路徑的上一鄰居節(jié)點(diǎn)集合為{v1,v2,…,vk},則節(jié)點(diǎn)u將列表集合添加到必需的鄰居節(jié)點(diǎn)集合Required中并刪除冗余鏈路集合N1(u)-{v1,v2,…,vk},調(diào)整功率為到達(dá){v1,v2,…,vk}中最遠(yuǎn)節(jié)點(diǎn)的功率,然后在鄰域內(nèi)逆向廣播一個(gè)Notify(ID(u),{v1,v2,…,vk})消息。假設(shè)節(jié)點(diǎn)vi收到該信息后,則解析消息并將發(fā)送節(jié)點(diǎn)ID與k條可達(dá)路徑的鄰居節(jié)點(diǎn)集合為{v1,v2,…,vk}合并,然后調(diào)整最大功率并繼續(xù)上述過程直到Notify消息到達(dá)執(zhí)行器節(jié)點(diǎn),算法終止。

圖1 MSFT算法具體運(yùn)行實(shí)例

圖1給出了MSFT算法的具體運(yùn)行實(shí)例,其中1(0.8),2(0.6),3(0.8),4(0.7)表示傳感器節(jié)點(diǎn),5(10),6(10),7(10)表示執(zhí)行器節(jié)點(diǎn),括號(hào)中數(shù)值表示節(jié)點(diǎn)的初始能量,鏈路上的數(shù)值表示通信鏈路功耗。初始時(shí),假設(shè)各執(zhí)行器節(jié)點(diǎn)分別發(fā)送PathInfo(hops=2)消息,各傳感器節(jié)點(diǎn)收到路徑消息后最終形成排序后的PathList列表如圖1(b)-(e)所示,黑色加粗記錄表示不相交路徑,圖1(f)給出了各個(gè)節(jié)點(diǎn)調(diào)整功率后的最終拓?fù)洹?/p>

4 性能分析

定理1假設(shè)初始網(wǎng)絡(luò)中各傳感器節(jié)點(diǎn)與執(zhí)行器節(jié)點(diǎn)是k連通的,那么通過MSFT形成的最終拓?fù)淙匀皇莐連通的。

證明假設(shè)節(jié)點(diǎn)u和v之間的鏈路(u,v)被刪除。MSFT算法為了節(jié)省能量在保證k條通路后會(huì)調(diào)整節(jié)點(diǎn)功率為Required集合的最大值,即說明v不在u的Required集合中。因?yàn)槌跏季W(wǎng)絡(luò)是k連通的,Required集合確保了至少存在k條通向執(zhí)行器節(jié)點(diǎn)的鏈路,因此刪除鏈路v并不影響網(wǎng)絡(luò)的連通性,否則u并不會(huì)刪除鏈路(u,v),所以通過MSFT形成的最終拓?fù)淙匀慌c各執(zhí)行器節(jié)點(diǎn)k連通。

定理2MSFT的時(shí)間和信息復(fù)雜度均為O(n)。

證明節(jié)點(diǎn)計(jì)算路徑功耗并轉(zhuǎn)發(fā)消息均能在常數(shù)時(shí)間內(nèi)完成,因此該部分時(shí)間復(fù)雜度為O(1)。超時(shí)timer結(jié)束后,節(jié)點(diǎn)需要對(duì)存儲(chǔ)的所有可達(dá)執(zhí)行器節(jié)點(diǎn)的有效路徑列表PathList進(jìn)行排序,因此需要O(plogp)的時(shí)間,其中p表示節(jié)點(diǎn)在超時(shí)timer內(nèi)收到的路徑集合數(shù),假設(shè)節(jié)點(diǎn)鄰域存在Δ個(gè)鄰居節(jié)點(diǎn),則p在最壞情況下等于kΔ。在得到k條不相交路徑列表K-Connective-Path的過程中,需要比較NPathList與K-Connective-Path列表中的每一條記錄的路徑相交性,因此需要O(k2hlogh)的時(shí)間復(fù)雜度,其中h表示距離執(zhí)行器節(jié)點(diǎn)的跳數(shù)。在鄰域節(jié)點(diǎn)的標(biāo)記過程中,節(jié)點(diǎn)以O(shè)(Δ)的時(shí)間生成k條可達(dá)路徑的上層鄰居節(jié)點(diǎn)集合為{v1,v2,…,vk},該過程中算法的時(shí)間復(fù)雜度為O(Δ),因?yàn)閗,h均為常數(shù),因此MSFT總的時(shí)間復(fù)雜度為O(n)。同時(shí),網(wǎng)絡(luò)節(jié)點(diǎn)為了搜集k條到達(dá)執(zhí)行器節(jié)點(diǎn)的可達(dá)路徑,在最壞情況下需要將本地消息包轉(zhuǎn)發(fā)k次;而在標(biāo)記鄰居節(jié)點(diǎn)的過程中,每一個(gè)節(jié)點(diǎn)均需要廣播一次Notify消息,因此所有節(jié)點(diǎn)最壞需要發(fā)送k+1次的消息,算法的消息復(fù)雜度為O(n)。

5 仿真實(shí)驗(yàn)及分析

5.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

為了驗(yàn)證算法的性能,本文在基于網(wǎng)絡(luò)事件驅(qū)動(dòng)的仿真平臺(tái)Atarraya[21]上進(jìn)行實(shí)驗(yàn)。節(jié)點(diǎn)隨機(jī)部署在200×200的區(qū)域內(nèi),假設(shè)所有節(jié)點(diǎn)的初始能量異構(gòu)分布在范圍[0.5,1]中,傳輸距離設(shè)置在范圍[5,35]之間對(duì)應(yīng)最小和最大功率范圍[25,1225],這里不考慮執(zhí)行器節(jié)點(diǎn)之間的數(shù)據(jù)傳輸,并保證生成的拓?fù)錆M足k-ATC。選擇與算法DATC(h=1)和DATC(h=2)進(jìn)行對(duì)比,實(shí)驗(yàn)結(jié)果取自運(yùn)行20次后的平均值,具體參數(shù)如表1所示。

表1 仿真參數(shù)

5.2 實(shí)驗(yàn)結(jié)果分析

第1組實(shí)驗(yàn)通過改變節(jié)點(diǎn)數(shù)量觀察容錯(cuò)k=2時(shí)的各個(gè)算法產(chǎn)生的拓?fù)溥\(yùn)行功率、節(jié)點(diǎn)的最大功率和消息發(fā)送數(shù)的情況。圖2顯示了當(dāng)k=2時(shí)網(wǎng)絡(luò)的最終拓?fù)涞倪\(yùn)行功耗情況。隨著傳感器節(jié)點(diǎn)密度的增加,各個(gè)算法的功耗均不斷增加,同時(shí)發(fā)現(xiàn)MSFT算法相比DATC(h=1)和DATC(h=2)具有更好的性能,這是因?yàn)镸SFT在選擇k條不相交路徑時(shí)能夠獲得距離執(zhí)行器節(jié)點(diǎn)功耗更低的傳輸路徑,而DATC(h=1)和DATC(h=2)由于將傳輸路徑的選擇限制在一跳鄰域或二跳鄰域?qū)е铝诵阅艿南陆怠?/p>

圖2 最終拓?fù)涞倪\(yùn)行功耗(k=2)

網(wǎng)絡(luò)的生命時(shí)間不僅和消耗的總功率有關(guān),還與網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗速度有關(guān)。如果個(gè)別節(jié)點(diǎn)能耗過大,那么形成網(wǎng)絡(luò)拓?fù)鋵?huì)由于部分節(jié)點(diǎn)的提前死亡而出現(xiàn)中斷,這就需要盡可能地平衡網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的能耗。圖3顯示了當(dāng)k=2時(shí)的網(wǎng)絡(luò)中所有節(jié)點(diǎn)的最大功率情況。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的密度逐漸增加時(shí),MSFT算法所需要的節(jié)點(diǎn)最大功率不斷下降,這是由于MSFT能夠在本地獲得性能更好的不相交路徑。同時(shí),不管是DATC(h=1)還是DATC(h=2)都將由于部分節(jié)點(diǎn)的功耗過大導(dǎo)致網(wǎng)絡(luò)提前死亡。

圖3 網(wǎng)絡(luò)節(jié)點(diǎn)的最大功率(k=2)

拓?fù)淇刂扑惴ǖ暮脡牟粌H與最終產(chǎn)生的網(wǎng)絡(luò)拓?fù)涞倪\(yùn)行功耗有關(guān),還與產(chǎn)生拓?fù)溥^程中的能耗有關(guān),本文使用節(jié)點(diǎn)發(fā)送的消息數(shù)量近似衡量構(gòu)建能耗。圖4顯示了各個(gè)算法發(fā)送的信息數(shù)量情況。之前實(shí)驗(yàn)顯示DATC(h=2)相比DATC(h=1)在最終產(chǎn)生的拓?fù)溥\(yùn)行功率以及節(jié)點(diǎn)的最大功率上性能更優(yōu),但是發(fā)現(xiàn)其需要發(fā)送的信息數(shù)量呈幾何指數(shù)性增長,這是因?yàn)樗惴ㄔ讷@得不相交鏈路的過程中需要獲得二跳鄰域范圍的節(jié)點(diǎn)信息,因此通信能耗極大并不適合在真實(shí)網(wǎng)絡(luò)中應(yīng)用。MSFT相比DATC(h=1)發(fā)送的信息數(shù)更少,因此在構(gòu)建拓?fù)溥^程中將節(jié)省更多的能量。

圖4 拓?fù)錁?gòu)建過程的信息發(fā)送數(shù)(k=2)

圖5 最終拓?fù)涞倪\(yùn)行功耗(k=4)

第2組實(shí)驗(yàn)通過改變節(jié)點(diǎn)數(shù)量觀察容錯(cuò)k=4時(shí)各個(gè)算法的性能。發(fā)現(xiàn)當(dāng)k變大后無論節(jié)點(diǎn)密度如何各個(gè)算法的功率均有所增加,這是因?yàn)闉榱吮ＷC每個(gè)節(jié)點(diǎn)存在至少k條到達(dá)執(zhí)行器節(jié)點(diǎn)的路徑,隨著k的增加更多的邊集需要被維護(hù),因此會(huì)導(dǎo)致功率的增加。同時(shí)當(dāng)k增加時(shí),需要發(fā)送的信息數(shù)也會(huì)相應(yīng)的增加。與之前實(shí)驗(yàn)類似,無論是在最終產(chǎn)生的拓?fù)溥\(yùn)行功率、節(jié)點(diǎn)的最大功率還是消息發(fā)送數(shù),MSFT算法均具有較優(yōu)的性能。

圖6 網(wǎng)絡(luò)節(jié)點(diǎn)的最大功率(k=4)

圖7 拓?fù)錁?gòu)建過程的信息發(fā)送數(shù)(k=4)

6 總結(jié)

本文在由執(zhí)行器節(jié)點(diǎn)和傳感器節(jié)點(diǎn)組成的多源異構(gòu)無線傳感器網(wǎng)絡(luò)中定義了k-ATC問題并提出了一種能量高效的容錯(cuò)拓?fù)淇刂扑惴∕SFT。MSFT通過功率控制的方法確保每個(gè)傳感器節(jié)點(diǎn)至少存在k條到達(dá)一個(gè)或多個(gè)執(zhí)行器節(jié)點(diǎn)的不相交路徑,然后將功率調(diào)整到與最遠(yuǎn)鄰居節(jié)點(diǎn)通信所需要的功率以節(jié)約能量。因此,當(dāng)網(wǎng)絡(luò)中任意k-1個(gè)節(jié)點(diǎn)發(fā)生故障時(shí),網(wǎng)絡(luò)不會(huì)終止。同時(shí),仿真實(shí)驗(yàn)證實(shí),MSFT產(chǎn)生的最終運(yùn)行拓?fù)涔β氏啾韧愃惴―ATC能夠提高大約3倍的性能,因此適合應(yīng)用在節(jié)點(diǎn)受到環(huán)境影響而頻繁失效的惡劣網(wǎng)絡(luò)環(huán)境。下一步的工作將主要考慮將MSFT算法在物理層和MAC層等不同層次進(jìn)行跨層優(yōu)化,同時(shí)可移動(dòng)的執(zhí)行器節(jié)點(diǎn)部署也是一個(gè)研究方向。

[1] Yick J,Mukherjee B,Ghosal D. Wireless Sensor Network Survey[J]. Computer Networks,2008,52(12):2292-2330.

[2] Anastasi G,Conti M,Francesco M,et al. Energy Conservation in Wireless Sensor Networks:A Survey[J]. Ad Hoc Networks,2009,7(3):537-568.

[3] Labrador M A,Wightman P M. Topology Control in Wireless Sensor Networks[M]. Berlin:Springer,2009:61-68.

[4] Liu H,Nayak A,Stojmenovic I. Fault-Tolerant Algorithms/Protocols in Wireless Sensor Networks[C]//Guide to Wireless Sensor Networks,2009:265-295.

[5] Yarvis M,Kushalnagar N,Singh H,et al. Exploiting Heterogeneity in Sensor Networks[C]//Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies(IEEE INFOCOM),Miami,USA,2005:878-890.

[6] 周雁,王福豹,黃亮,等. 無線傳感器執(zhí)行器網(wǎng)絡(luò)綜述[J]. 計(jì)算機(jī)科學(xué),2012,39(10):21-25.

[7] 孫超,尹榮榮,郝曉辰,等. WSNs 中基于能量代價(jià)的最小權(quán)和支配集拓?fù)淇刂扑惴╗J]. 電子與信息學(xué)報(bào),2010,32(4):857-863.

[8] 孫超,尹榮榮,郝曉辰,等. 異構(gòu)無線傳感器網(wǎng)絡(luò)支配集拓?fù)淇刂扑惴╗J]. 軟件學(xué)報(bào),2011,22(9):2137-2148.

[9] Du H W,Wu W L,Ye Q,et al. CDS-Based Virtual Backbone Construction with Guaranteed Routing Cost in Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2013,24(4):652-661.

[10] Kubisch M,Karl H,Wolisz A,et al. Distributed Algorithms for Transmission Power Control in Wireless Sensor Networks[C]//IEEE Wireless Communications and Networking Conference(WCNC),New York,USA,2003:16-20.

[11] 陳友榮,俞立,董齊芬,等. 基于近鄰算法的無線傳感器網(wǎng)絡(luò)功率控制[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版),2010,44(7):1321-1326.

[12] 郝曉辰,張亞曉,劉彬,等. 一種能耗均衡的傳感器網(wǎng)絡(luò)可靠拓?fù)洳┺乃惴╗J]. 軟件學(xué)報(bào),2011,22(增1):1-12.

[13] 陳友榮,任條娟,劉半藤,等. 基于最短路徑樹的分布式功率控制路由算法[J]. 傳感技術(shù)學(xué)報(bào),2012,25(8):1138-1146.

[14] Li N,Hou J C. Localized Fault-Tolerant Topology Control in Wireless Ad Hoc Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2006,17(4):307-320.

[15] Miyao K,Nakayama H,Ansari N,et al. LTRT:An Efficient and Reliable Topology Control Algorithm for Ad-Hoc Networks[J]. IEEE Transactions on Wireless Communications,2009,8(12):6050-6058.

[16] Li N,Hou J C,Sha L. Design and Analysis of an MST-Based Topology Control Algorithm[C]//Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies,San Francisco,USA,2003:1702-1712.

[17] Azzeddine R,Wang D. SFL:A Simple Fault-Tolerant Local Topology Control algorithm for sensor networks[C]//IEEE Conference on Industrial Electronics and Applications(ICIEA),Singapore,2012.

[18] Cardei M,Yang S,Wu J. Algorithms for Fault-Tolerant Topology in Heterogeneous Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2008,19(4):545-558.

[19] 楊明霞,王萬良,馬晨明. 一種基于反向CDS樹的異構(gòu)WSNs拓?fù)錁?gòu)建方法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(2):248-255.

[20] 楊明霞,王萬良,馬晨明. 面向節(jié)能和容錯(cuò)的異構(gòu)WSNs數(shù)據(jù)收集算法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(6):934-940.

[21] Wightman P M,Labrador M A. Atarraya:A Simulation Tool to Teach and Research Topology Control Algorithms for Wireless Sensor Networks[C]//Proceedings of 2nd International Conference on Simulation Tools and Techniques,Rome,Italy,2009:26-35.

楊明霞(1979-),女,博士,衢州學(xué)院講師。主要研究方向?yàn)橹悄苄畔⑻幚?、無線傳感器網(wǎng)絡(luò),ymx1228@163.com;

畢宏博(1984-),男,博士,講師,目前研究方向?yàn)榈鷮W(xué)習(xí)控制,bihbo001@163.com;

柴國飛(1986-),男,博士,衢州學(xué)院講師,主要研究方向?yàn)槎嘀悄荏w系統(tǒng)、無線傳感器網(wǎng)絡(luò),guofei.chai@gmail.com。

MultipleSourceFault-TolerantTopologyControlMethodResearchinWirelessSensorandActorNetwork*

YANGMingxia*,BIHongbo,CHAIGuofei

(College of Electrical and Information Engineering,QuZhou University,Quzhou 324000,China)

Topology Control is a key strategy to extend the lifetime of wireless sensor networks. In the light of the complication in the heterogeneous network,a distributed multiple source fault-tolerant topology control algorithm MSFT based on power control is proposed. In the heterogeneous network model which is composed of a large number of sensor nodes with limited energy and computing capability,and several actors with unlimited energy resources,the algorithm ensure each sensor has at leastk-vertex disjoint paths to actors and choose node with better weight to minimal the total path power consumption. The resulting topologies can keep network connectivity even in case of thek-1 node failures. Theoretical analysis show MSFT is able to construct the topology with time and message complexity ofO(n)and simulation results confirm the effectiveness of the algorithm further.

wireless sensor and actor network;heterogeneous;fault tolerant;topology control;power control

TP393

A

1004-1699(2017)11-1740-07

項(xiàng)目來源:浙江省自然科學(xué)基金(LQ17F030005);衢州市科技計(jì)劃項(xiàng)目(2016Y001,2016D005);衢州學(xué)院師資隊(duì)伍建設(shè)基金(XNZQN201308);衢州學(xué)院人才培養(yǎng)科研啟動(dòng)項(xiàng)目(BSYJ201505)

2017-03-15修改日期2017-06-01

10.3969/j.issn.1004-1699.2017.11.021