基于節點可靠度的無線傳感器網絡拓撲控制算法

劉洲洲,彭 寒

(1.西安航空學院 電子工程學院,西安710077;2.西北工業大學 計算機學院,西安710072)

0 引 言

無線傳感器網絡(WSN)作為物聯網發展的重要組成部分[1,2],與其他通信網絡相比,具有部署規模大、節點冗余度高、分布環境惡劣和節點自身資源有限等特點[3]。對于大規模部署的WSN,良好的拓撲結構是網絡生存能力的重中之重[4],也是實現各種網絡協議的基礎。

當前對于WSN拓撲結構控制算法大多是從節能角度出發考慮的,其中,文獻[5]構建了一種節能拓撲(Energy-aware evolution model,EAEM),節點的擇優連接概率不僅僅取決于節點度,還與節點的剩余能量有關。文獻[6]在局域世界內建立適應度模型,通過調節節點的適應度因子,最終演化出能耗更均衡的無標度拓撲,更適用于WSN的實際應用。文獻[7]構建的拓撲,通過節點的剩余能量限制網絡中的最大節點度,有效地均衡了網絡負載,減小了能量耗盡對拓撲的影響。文獻[8]基于節點綜合故障模型約束網絡節點度,構建了節能容錯的拓撲結構。然而,目前工程上所用的WSN節點大多受到節點能量和容量的限制,其中節點容量是指節點能夠轉發數據量多少的能力,現有WSN拓撲控制算法大多僅僅考慮節點能量方面的優化,考慮節點容量方面的研究較少,而節點容量正是引起節點擁塞的重要原因,目前研究的節點擁塞控制機制都是在節點發生擁塞時才采取一定的擁塞控制措施。其中,文獻[9]通過分析得出,距離SINK節點越近的節點越容易發生擁塞,然后依據節點距離SINK節點的遠近控制節點度,最終達到控制網絡數據擁塞的目的。文獻[10,11]通過判斷節點緩存內數據隊列長度來判斷節點的擁塞程度,然后通過控制節點度達到減弱拓撲擁塞的目的。文獻[12]運用博弈理論來分析單個傳感器節點的分布式決策過程,以此達到降低網絡能耗的目的,但是僅在理論層面上給出了理想的能耗均衡WSN結構,并沒有考慮節點度對網絡性能的影響。文獻[13]考慮了節點在廣播時的干擾和能量消耗,通過優化每個節點的傳動功率以達到優化網絡結構的目的,以此來降低節點擁塞。文獻[14]從博弈論的視角出發考慮單個節點度對網絡性能的影響,從理論上分析了WSN系統存在最優的納什均衡。但是,以上文獻均沒有考慮到當無線傳感器網絡節點大規模密集部署時,在突發數據流引發擁塞后,再采用擁塞控制措施也不一定可以完全避免節點擁塞,則很有可能導致節點能量過快耗盡,進而導致全局網絡受損。

針對上述分析,本文提出了一種基于節點可靠度拓撲控制算法(Topology control based on node reliability in wireless sensor networks,TCNR),首先依據節點能量耗盡概率和擁塞失效概率構建節點可靠度模型,并以節點可靠度最大和網絡生存時間最長為約束條件,獲得了最優節點度的取值,最終通過最優節點度約束網絡所有節點的節點度,根據僅改變最優節點度取值,可以有效地使整個網絡拓撲性能得到優化,從而達到延長網絡生存時間的目的。

1 問題模型

WSN在數據傳輸過程中,節點能量耗盡和數據擁塞是造成數據傳輸失敗的重要原因,本文通過對節點能量耗盡失效概率和數據擁塞造成節點失效概率建模,得出了節點可靠度模型,并通過分析節點可靠度與網絡參數的關系,最終得出了最優節點度的取值。

1.1 節點可靠度建模

本文將節點i可靠度R(i)定義為:

式中:fe(i)為節點i能量耗盡失效的概率;fc(i)為節點i數據擁塞造成節點失效的概率。

節點能量耗盡失效和數據擁塞造成節點失效的概率越大,節點的可靠度就越小;節點能量耗盡失效和數據擁塞造成節點失效的概率越小,節點的可靠度就越大。

由文獻[15]可知,節點能量耗盡的概率fe(i)取決于節點i的初始能量值E0(i)、能量消耗值Ec(i)和網絡運行時間t,即:

采用一階無線通信能耗模型[16],兩個相距為d的節點發送lbit數據所消耗的能量Etx為:

式中:Eelec為射頻傳輸系數;εamp為發送裝置放大系數。

節點接收lbit數據消耗能量Erx取決于信號接收電路消耗的能量:

那么,節點i在單位時間內消耗的總能耗Ec(i)可由下式計算得到:

假設N個節點隨機部署在監測區域G(面積為A)上,由概率論可知節點坐標(X,Y)具有概率密度函數g(x,y)為:

則節點落入以通信距離d為半徑的圓域D內的概率P為:

因此,可得節點傳輸距離d與其節點度k之間存在如下關系:

此時,將式(8)代入式(5),可得節點i的能耗值Ec(i)隨其節點度k的變化關系:

再將式(9)代入式(2)可得節點由能量耗盡引起節點失效的概率fe(i)為:

考慮到WSN引起節點擁塞的重要原因是其負載大于其最大容量。通常WSN節點負載是指節點在某一時刻需要轉發的信息量,假設節點i的節點度為k,任意節點與其鄰居節點數據交換的信息量為l,那么在任意時刻節點i的最大負載L定義為:

由于WSN節點受到硬件資源的限制,節點具有固定的容量,如果在某一時刻其負載量超過其容量,就會發生擁塞。其中,節點發生擁塞的概率與其負載量成正比,節點負載量越大,其發生擁塞的概率就越大。假設節點擁有固定的容量C0,那么在任意時刻節點由數據擁塞是造成節點失效的概率fc(i)定義為:

為了滿足概率范圍為[0,1]的條件,式(12)中C0－kl＞1,可得,將式(10)和式(12)代入式(1)可得節點可靠度函數為:

式(13)即為節點可靠度數學模型,由式(13)可知,節點可靠度不僅與節點度有關,也與網絡的生存時間相關。下面利用所獲得的節點可靠度數學模型對節點度進行量化分析,為獲取依據最優節點度調整的WSN拓撲演化模型提供理論依據。

1.2 基于節點可靠度的最優節點度量化分析

對于一個網絡I,其拓撲參數應滿足如下條件:為提高拓撲的可用性,網絡須保證一定的生存時間tmin,即t≥tmin;為了保證網絡的連通性,網絡I須維持一定的節點度下限kmin,即k～≥kmin。為了分析拓撲參數對節點可靠度的影響,得出網絡中節點可靠度最大時,網絡生存時間與節點度的關系,引出如下定理。

定理 對于一個網絡I,如果其運行時間t≥tmin,且網絡節點度符合,則當節點可靠度為時,網絡中的節點可靠度最大。其中,tmin為網絡預設運行時間,kmin為節點度下限,kmax為節點度上限值。

上述定理得出了網絡在節點可靠度最大時R0(i)與拓撲參數的關系,則當網絡中節點失效概率滿足R(i)＝R0(i),根據式(13)可得:

由于當式(17)中分子1－(C0－kl)(1－R0(i))＜0時,函數值不存在,因此可得:

由于0＜1－(C0－kl)(1－R0(i))＜1,所以ln[1－(C0－kl)(1－R0(i))]＜0,又且(a＋bk)2＞0,因此可得t′＜0,也就是說,式(17)在范圍內單調遞減,由于節點度k為整數,因此可得:當時,網絡生存時間最長。

綜上可知,由于突發數據流引發擁塞后,再采用擁塞控制措施也不一定可以完全避免節點擁塞,很有可能導致節點能量過快耗盡,本文通過理論分析獲得了在節點可靠度最大和網絡生存時間最長的條件下最優節點度k0的取值,通過最優節點度約束網絡所有節點的節點度,相比目前已有的研究[10-14],根據僅改變最優節點度取值,優化了網絡拓撲性能,延長了網絡生命周期。

2 TCNR算法

TCNR算法主要由以下4個階段組成:

(1)信息交換階段:在拓撲結構形成開始,各節點都以最大功率廣播“握手”消息,任意收到“握手”消息的節點建立其自身的鄰居列表。以節點i為例,鄰居列表的表頭格式如表1所示。其中,ID(j)表示節點i的鄰居節點j的ID;(x j,y j)表示節點j的地理位置;d(i,j)為i和j之間的距離;mark(j)為狀態標識,初始記為0。其中,任意節點的鄰居列表均依據節點之間的通信距離進行升序排序。

表1 節點i的鄰居列表的表頭格式Table 1 Header format for node i neighbor list

(2)鄰居排序階段:節點i廣播NOTICE信息,其中NOTICE信息包含節點iID及鄰居列表信息。收到NOTICE信息的鄰居節點判斷自身局域范圍內的通信狀態,并建立局域鏈路列表,其表頭格式見表2。其中,假設j1、j2為節點i的鄰居節點,d(j1,j2)為節點i的鄰居節點j1和j2間的距離,ID(j1)和ID(j2)分別為j1、j2的ID,sign(j1,j2)為狀態標識,初始設定為0。區域鏈路列表建立后,節點i按照通信距離d(j1,j2)對其局域鏈路列表進行升序排列,如果j1和j2之間不存在通信路徑,將鏈路狀態標識sign(j i,j j)更新為1,直至與所有鄰節點判斷完成為止,最后刪除sign標記為0的鏈路項信息。

表2 節點i局域鏈路列表的表頭格式Table 2 Header format for node i local link list

(3)鏈路選擇階段:依據區域鏈路列表,節點i對其鄰居節點廣播包含自身ID和局域鏈路列表信息的CONNECT數據包。根據所接收到的CONNECT數據,以鏈路雙向性原則確定其區域鏈路,將其sign標記為2,刪除標記為1的鏈路項信息,進而尋找區域鏈路列表中由自身出發的鏈路項,并將其鄰居列表中的相應標識位mark更新為1,統計其數目記為kmin,計算出最優節點度k0與kmin的差值k^。在此基礎上,按距離升序依次將k^個鄰居列表中標識為0的節點標記為2,刪除狀態不為1的鄰節點信息項。

(4)功率調整階段:節點i根據鏈路選擇階段確定其自身發射功率,同時應保證與新的鄰居節點皆能正常通信。

3 仿真實驗與性能分析

為了驗證TCNR拓撲控制算法的性能,本文采用MATLAB 2012a仿真工具,對具有節能代表性的FTEL算法[16]和路徑優化算法(Path optimization algorithm,POA)[17]進行仿真實驗對比,并且假定拓撲結構均為不分簇的同構平面結構,仿真實驗參數見表3。其中,每一個實驗結果都是50次實驗的平均值。

表3 實驗環境參數Table 3 Experimental environmental parameters

為了解析得到網絡中最優節點度k0的最優取值,首先根據構建的節點可靠度模型和表3中的參數取值,并結合式(18)可以得出最優節點度在k0＝4時網絡運行時間達到最大,然后依據TCNR拓撲控制算法優化網絡拓撲,與FTEL和POA算法進行性能對比。

3.1 拓撲結構對比

在1000 m×1000 m的區域隨機布撒100個節點,依照TCNR、FTEL和POA三種拓撲控制算法得到的拓撲結構如圖1所示。對比TCNR和FTEL拓撲結構可以看出,FTEL中存在較多度為1的節點和一部分度較大的節點,而TCNR圖譜結構較為均勻,拓撲中的節點度都接近4,可以有效避免節點擁塞和能量耗盡失效。TCNR與POA拓撲相比,大大減少了冗余鏈路的存在,有效避免了不必要的節點能耗,延長了絡生存時間。

圖1 拓撲結構對比Fig.1 Comparison of topological structure

3.2 網絡平均節點度對比

網絡的平均節點度通常表示為節點與鄰居節點通信鏈路的數量,因此,拓撲連通的情況下可以通過平均節點度的大小來衡量拓撲的冗余程度和干擾程度,如果平均節點度越大,冗余鏈路越多就會造成網絡能耗越快,而且鏈路之間的干擾也會增大,本文對TCNR、FTEL和POA三種拓撲控制算法的平均節點度進行了對比。分別在1000 m×1000 m的區域隨機布撒100、200、300、400和500個節點,依照TCNR、FTEL和POA三種拓撲控制算法,得到3種拓撲結構的平均節點度如圖2所示。由圖2可以看出,TCNR算法的平均節點度在5左右,POA算法平均節點度在7左右,FTEL算法隨節點數的增加平均節點度也在逐漸增大。TCNR算法與POA和FTEL算法相比比降低了網絡平均節點度,說明TCNR算法通過最優節點度的限制有效控制了網絡的平均節點度,減少了網絡干擾,增強了網絡健壯性。

圖2 平均節點度對比Fig.2 Comparison of average node degree

3.3 網絡健壯性對比

網絡在數據傳輸過程中通常會伴隨著節點失效,當節點失效后,拓撲中剩余最大連通分支的數目可以作為網絡健壯性的衡量標準。為了對比3種網絡的健壯性,在1000 m×1000 m的區域隨機布撒100個節點,依照TCNR、FTEL和POA三種拓撲控制算法運行拓撲,在每輪數據傳輸過程中,節點均與其鄰居節點進行數據交換,節點按照一階能耗模型計算剩余能量[12],節點在能量耗盡和擁塞時均按照死亡節點處理,最后統計網絡中剩余最大連通分支節點數目,剩余最大連通數目越大表示網絡健壯性越好,得到的網絡健壯性對比圖如圖3所示。由圖3可以看出,3種拓撲結構在網絡運行1000輪的情況下,TCNR拓撲剩余最大連通數目將近80%,POA拓撲剩余最大連通分支將近50%,FTEL拓撲剩余最大連通分支僅剩22%左右,說明TCNR算法通過拓撲控制有效提高了拓撲結構的健壯性。

圖3 網絡健壯性對比Fig.3 Comparison of network robustness

3.4 網絡生命期對比

網絡的生存時間通常定義為首節點失效的時間,也就是說,在數據傳輸過程中,拓撲中出現首個節點失效的時間可以作為網絡生命期的衡量標準。因此,在仿真實驗中將拓撲出現首節點失效的時間記為網絡的生存時間,圖4給出了TCNR、FTEL和POA三種模型的網絡生存時間,從圖4中可以看出,TCNR算法擁有最長的網絡生命期,相對POA算法的網絡生命期提升了將近30%,相對FTEL提升了將近50%,說明TCNR拓撲通過控制網絡節點度有效均衡了網絡能耗,延長了網絡生命期。

圖4 網絡生命期對比Fig.4 Comparison of network life cycle

4 結束語

通過構建節點可靠度模型以及理論分析得出了在節點可靠度最大且網絡生存時間最長的條件下的最優節點度,進而依據最優節點度提出了一種基于節點度調整的拓撲控制算法TCNR。最后,通過仿真驗證了該拓撲的節能性和可靠性。利用TCNR模型,僅通過改變最優節點度取值就可以產生綜合性能優化的拓撲,為WSN拓撲控制算法奠定了良好的基礎。今后研究工作的重點是,在實際應用環境下測試本文工作的有效性以提高其實用性。

[1]Lin T Y,Santoso H A,Wu K R.Global sensor deployment and local coverage-aware recovery schemes for smart environments[J].IEEE Transactions on Mobile Computing,2015,14(7):1382-1396.

[2]Mahboubi H,Moezzi K,Aghdam A G,et al.Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors[J].IEEE Transactions on Industrial Informatics,2014,10(1):163-174.

[3]Mahboubi H.Distributed deployment algorithms for efficient coverage in a network of mobile sensors with no identical sensing capabilities[J].IEEE Transactions on Vehicular Technology,2014,63(8):3998-4016.

[4]Mahboubi H,Aghdam A G.Distributed deployment strategies to increase coverage in a network of wireless mobile sensors[C]∥Proceedings of 2013 A-merican Control Conference(ACC),Washington,2013:17-19.

[5]Zhu H L,Luo H,Peng H P,et al.Complex networks-based energy-efficient evolution model for wireless sensor networks[J].Chaos,Solitons and Fractals,2009,41(4):1828-1835.

[6]Qi X Q,Ma S Q,Zheng G Z.Topology evolution of wireless sensor networks based on adaptive freescale network[J].Journal of Information and Computational Science,2011,8(3):467-475.

[7]張德干,戴文博,牛慶肖.基于局域世界的WSN拓撲加權演化模型[J].電子學報,2012,40(5):1000-1004.Zhang De-gan,Dai Wen-bo,Niu Qing-xiao.Structure of WSN topological weighted evolution model based on local domain[J].Acta Electronic Journal,2012,40(5):1000-1004.

[8]王亞奇,楊曉元.一種無線傳感器網絡簇間拓撲演化模型及其免疫研究[J].物理學報,2012,61(9):090202.Wang Ya-qi,Yang Xiao-yuan.Study on cluster evolution model and its immunity of wireless sensor networks[J].Acta Physica Sinica,2012,61(9):090202.

[9]尹榮榮,劉彬,劉浩然,等.無線傳感器網絡中無標度拓撲的動態容錯性分析[J].物理學報,2014,63(11):110205.Yin Rong-rong,Liu Bin,Liu Hao-ran,et al.Dynamic fault tolerance analysis of scale-free topologies in wireless sensor networks[J].Acta Physica Sinica,2014,63(11):110205.

[10]Bartolini N,Calamoneri T,Portat T FL,et al.Autonomous deployment of heterogeneous mobile sensors[J].IEEE Transactions on Mobile Computing,2011,10(6):753-766.

[11]Chen I R,Speer A P,Eltoweissy M.Adaptive faulttolerant QoS control algorithm for maximizing system lifetime of query-based wireless sensor networks[J]. IEEE Transactions on Dependable and Secure Computing,2011,8(2):161-176.

[12]Ren H,Meng Q H.Game-theoretic modeling of joint topology control and power scheduling for wireless heterogeneous sensor networks[J].IEEE Transactions on Automation Science&Engineering,2009,6(4):610-625.

[13]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,2010,8(12):6050-6058.

[14]Nahir A,Orda A,Freund A.Topology design of communication networks:a game-theoretic perspective[J].IEEE/ACM Transactions on Networking,2014,22(2):405-414.

[15]尹榮榮,劉彬,李雅倩,等.能量異構無線傳感器網絡容錯拓撲研究[J].電子與信息學報,2012,34(9):2180-2186.Yin Rong-rong,Liu Bin,Li Ya-qian,et al.Study on fault tolerant topology of energy heterogeneous wireless sensor networks[J].Journal of Electronics&Information Technology,2012,34(9):2180-2186.

[16]劉浩然,尹文曉,韓濤,等.一種優化傳感器無線網絡生命周期的容錯拓撲研究[J].物理學報,2014,63(4):80-86.Liu Hao-ran,Yin Wen-xiao,Han Tao,et al.Wireless sensor network fault tolerant topology for lifetime optimization[J].Acta Phys Sin,2014,63(4):80-86.

[17]郝曉辰,劉偉靜,辛敏潔,等.一種無線傳感器網絡健壯性可調的能量均衡拓撲控制算法[J].物理學報,2015,64(8):080101.Hao Xiao-chen,Liu Wei-jing,Xin Min-jie,et al.An energy balance topology control algorithm for robustness of wireless sensor networks[J].Acta Physica Sinica,2015,64(8):080101.