楊明霞,畢宏博,柴國飛

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

無線傳感執(zhí)行器網(wǎng)絡(luò)中多源容錯拓撲控制算法研究*

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

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

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

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

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

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

本文在WSANs的基礎(chǔ)上研究容錯拓撲控制算法,提出了MSFT(Multiple Source Fault-Tolerant Algorithm)用于保證網(wǎng)絡(luò)中任意Sensor節(jié)點至少存在k條到達Actor的不相交路徑,如果網(wǎng)絡(luò)是k連通的,那么任意k-1個節(jié)點的失效不會導致網(wǎng)絡(luò)中斷,同時提高了網(wǎng)絡(luò)的路由靈活性。

1 相關(guān)工作

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

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

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

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

2 模型與問題描述

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

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

2.2 問題描述

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

定義1不相交路徑

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

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

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

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

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

(1)

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

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

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

(2)

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

消息傳輸失敗的概率隨著傳輸距離的增加而不斷變大,同時傳輸距離的增加將導致節(jié)點消耗的功率增大。另一方面,如果傳輸鏈路中存在能量水平較低的節(jié)點,那么網(wǎng)絡(luò)可能會由于個別節(jié)點的能量耗盡而提前死亡。本文定義式(3)～(6)用于衡量通信鏈路優(yōu)劣,其中Emin(ni,mj)和Pmax(ni,nj)分別表示當前路徑(ni,ni+1,ni+2,…,ni+p,mj)中所有路徑中間節(jié)點的最小能量和相鄰節(jié)點一跳路徑中功耗最大值。當鏈路的權(quán)值相等時比較一跳路徑中需要的功耗最大值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連接問題,同時使得優(yōu)化后的網(wǎng)絡(luò)拓撲鏈路總功率最小。假設(shè)網(wǎng)絡(luò)由傳感器節(jié)點N={v1,v2,…,vN}和執(zhí)行器節(jié)點M={vN+1,vN+2,…,vN+M}組成且N∩M=Φ。對于網(wǎng)絡(luò)中任意節(jié)點v∈V都至少存在k條能夠到達執(zhí)行器節(jié)點集合M的不相交路徑,同時使得這些路徑的通信鏈路權(quán)值之和最小。定義目標函數(shù)為:

(7)

3 MSFT算法描述

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

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

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

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

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

圖1 MSFT算法具體運行實例

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

4 性能分析

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

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

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

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

5 仿真實驗及分析

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

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

表1 仿真參數(shù)

5.2 實驗結(jié)果分析

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

圖2 最終拓撲的運行功耗(k=2)

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

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

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

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

圖5 最終拓撲的運行功耗(k=4)

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

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

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

6 總結(jié)

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

[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]. 計算機科學,2012,39(10):21-25.

[7] 孫超,尹榮榮,郝曉辰,等. WSNs 中基于能量代價的最小權(quán)和支配集拓撲控制算法[J]. 電子與信息學報,2010,32(4):857-863.

[8] 孫超,尹榮榮,郝曉辰,等. 異構(gòu)無線傳感器網(wǎng)絡(luò)支配集拓撲控制算法[J]. 軟件學報,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]. 浙江大學學報(工學版),2010,44(7):1321-1326.

[12] 郝曉辰,張亞曉,劉彬,等. 一種能耗均衡的傳感器網(wǎng)絡(luò)可靠拓撲博弈算法[J]. 軟件學報,2011,22(增1):1-12.

[13] 陳友榮,任條娟,劉半藤,等. 基于最短路徑樹的分布式功率控制路由算法[J]. 傳感技術(shù)學報,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拓撲構(gòu)建方法[J]. 傳感技術(shù)學報,2016,29(2):248-255.

[20] 楊明霞,王萬良,馬晨明. 面向節(jié)能和容錯的異構(gòu)WSNs數(shù)據(jù)收集算法[J]. 傳感技術(shù)學報,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-),女,博士,衢州學院講師。主要研究方向為智能信息處理、無線傳感器網(wǎng)絡(luò),ymx1228@163.com;

畢宏博(1984-),男,博士,講師,目前研究方向為迭代學習控制,bihbo001@163.com;

柴國飛(1986-),男,博士,衢州學院講師,主要研究方向為多智能體系統(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

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

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

10.3969/j.issn.1004-1699.2017.11.021