無線傳感執行器網絡中多源容錯拓撲控制算法研究*

楊明霞,畢宏博,柴國飛

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

無線傳感執行器網絡中多源容錯拓撲控制算法研究*

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

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

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

無線傳感執行器網絡;異構;容錯;拓撲控制;功率控制

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

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

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

1 相關工作

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

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

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

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

2 模型與問題描述

2.1 網絡模型

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

2.2 問題描述

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

定義1不相交路徑

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

定義2k連通網絡

無線傳感器網絡是k連通的當且僅當網絡中所有傳感器節點均存在k條通向執行器節點的不相交路徑。

定義3節點的初始功率設定

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

(1)

定義4節點之間的傳輸功率

本文采用式(2)的計算傳輸功率,假設任意節點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通信鏈路權值

消息傳輸失敗的概率隨著傳輸距離的增加而不斷變大,同時傳輸距離的增加將導致節點消耗的功率增大。另一方面,如果傳輸鏈路中存在能量水平較低的節點,那么網絡可能會由于個別節點的能量耗盡而提前死亡。本文定義式(3)～(6)用于衡量通信鏈路優劣,其中Emin(ni,mj)和Pmax(ni,nj)分別表示當前路徑(ni,ni+1,ni+2,…,ni+p,mj)中所有路徑中間節點的最小能量和相鄰節點一跳路徑中功耗最大值。當鏈路的權值相等時比較一跳路徑中需要的功耗最大值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問題

本文研究無線傳感執行器網絡的k連接問題,同時使得優化后的網絡拓撲鏈路總功率最小。假設網絡由傳感器節點N={v1,v2,…,vN}和執行器節點M={vN+1,vN+2,…,vN+M}組成且N∩M=Φ。對于網絡中任意節點v∈V都至少存在k條能夠到達執行器節點集合M的不相交路徑,同時使得這些路徑的通信鏈路權值之和最小。定義目標函數為:

(7)

3 MSFT算法描述

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

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

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

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

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

圖1 MSFT算法具體運行實例

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

4 性能分析

定理1假設初始網絡中各傳感器節點與執行器節點是k連通的,那么通過MSFT形成的最終拓撲仍然是k連通的。

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

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

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

5 仿真實驗及分析

5.1 實驗環境及參數設置

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

表1 仿真參數

5.2 實驗結果分析

第1組實驗通過改變節點數量觀察容錯k=2時的各個算法產生的拓撲運行功率、節點的最大功率和消息發送數的情況。圖2顯示了當k=2時網絡的最終拓撲的運行功耗情況。隨著傳感器節點密度的增加,各個算法的功耗均不斷增加,同時發現MSFT算法相比DATC(h=1)和DATC(h=2)具有更好的性能,這是因為MSFT在選擇k條不相交路徑時能夠獲得距離執行器節點功耗更低的傳輸路徑,而DATC(h=1)和DATC(h=2)由于將傳輸路徑的選擇限制在一跳鄰域或二跳鄰域導致了性能的下降。

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

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

圖3 網絡節點的最大功率(k=2)

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

圖4 拓撲構建過程的信息發送數(k=2)

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

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

圖6 網絡節點的最大功率(k=4)

圖7 拓撲構建過程的信息發送數(k=4)

6 總結

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

[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] 周雁,王福豹,黃亮,等. 無線傳感器執行器網絡綜述[J]. 計算機科學,2012,39(10):21-25.

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

[8] 孫超,尹榮榮,郝曉辰,等. 異構無線傳感器網絡支配集拓撲控制算法[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] 陳友榮,俞立,董齊芬,等. 基于近鄰算法的無線傳感器網絡功率控制[J]. 浙江大學學報(工學版),2010,44(7):1321-1326.

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

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

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

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

柴國飛(1986-),男,博士,衢州學院講師,主要研究方向為多智能體系統、無線傳感器網絡,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);衢州學院師資隊伍建設基金(XNZQN201308);衢州學院人才培養科研啟動項目(BSYJ201505)

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

10.3969/j.issn.1004-1699.2017.11.021