柳 艷,耿 鵬,楊 潔
(南京工程學(xué)院,江蘇 南京 211167)
狹長域無線傳感器網(wǎng)絡(luò)動態(tài)能量均衡控制
柳 艷,耿 鵬,楊 潔
(南京工程學(xué)院,江蘇南京211167)
針對基于連通支配集的無線傳感器網(wǎng)絡(luò)拓撲構(gòu)造算法在狹長域環(huán)境應(yīng)用中會存在能量失衡的問題,提出了狹長域無線傳感器網(wǎng)絡(luò)動態(tài)能量均衡控制方法。該方法基于A3、A3 Cov、EECDS和CDS Rule K等經(jīng)典拓撲構(gòu)造算法,將節(jié)點動態(tài)能量均衡的方法融入到上述算法之中,并對介數(shù)中心性重要節(jié)點進行了緩沖管理。在狹長區(qū)域內(nèi)布置隨機網(wǎng)絡(luò),對基于介數(shù)緩沖的動態(tài)能量均衡拓撲控制算法進行了仿真分析。結(jié)果表明,該算法能夠更加充分利用節(jié)點能量,延長了網(wǎng)絡(luò)壽命,提高了狹長域無線傳感器網(wǎng)絡(luò)的整體性能。
無線傳感器網(wǎng)絡(luò);狹長域;能量均衡;介數(shù)
無線傳感器網(wǎng)絡(luò)[1](Wireless Sensor Networks, WSN)是指在被探測區(qū)域中布置大量的傳感器節(jié)點,這些節(jié)點能夠形成一個自組織無線網(wǎng)絡(luò),每個節(jié)點通過無線信道和鄰居節(jié)點進行通信,以多跳方式將感應(yīng)數(shù)據(jù)傳遞到指定的集合位置(通常稱之為Sink節(jié)點)。由于應(yīng)用環(huán)境的惡劣性和節(jié)點數(shù)量的龐大性,導(dǎo)致網(wǎng)絡(luò)中節(jié)點往往難以補充能量[2],所以采取相應(yīng)的措施減少網(wǎng)絡(luò)能量消耗是無線傳感器網(wǎng)絡(luò)的重要研究課題。本文所關(guān)注的是從拓撲層面上對網(wǎng)絡(luò)結(jié)構(gòu)進行優(yōu)化控制,以達到節(jié)約能量的目的。
從數(shù)據(jù)的完整性和有效性來看,無線傳感器網(wǎng)絡(luò)存在的基本問題是:在保證網(wǎng)絡(luò)連通性和覆蓋率的前提條件下,盡量延長網(wǎng)絡(luò)的生命周期。連通性和覆蓋率可以通過增加傳輸半徑、感應(yīng)半徑和節(jié)點密度來進行保證,但這樣會帶來更多的能量消耗和更高的網(wǎng)絡(luò)成本[3]。一種有效的方法是網(wǎng)絡(luò)部署時保證一定的節(jié)點密度冗余;網(wǎng)絡(luò)運行時利用相關(guān)機制在不影響連通性和覆蓋率的同時關(guān)閉一部分節(jié)點,使沒有數(shù)據(jù)收發(fā)任務(wù)的節(jié)點進入睡眠狀態(tài);網(wǎng)絡(luò)運行到一定階段時再將這些睡眠節(jié)點逐次喚醒[4-6]。在無線傳感器網(wǎng)絡(luò)的研究中,使用較為廣泛的拓撲控制(Topology Control, TC)方法是在冗余網(wǎng)絡(luò)中尋找連通支配集(Connected Dominating Set, CDS),再在此集合中求解最小值,以構(gòu)建虛擬骨干網(wǎng)(Virtual Backbone Network, VBN)。求解最小連通支配集本質(zhì)上是NP-hard問題[7],無法得到精確答案,因此研究此問題的目的是在盡量平衡連通性、覆蓋率和生命周期的情況下,尋求一種近似最佳結(jié)果。文獻[8—11]所提出的基于連通支配集的無線傳感器網(wǎng)絡(luò)拓撲構(gòu)造算法在狹長域環(huán)境應(yīng)用中會存在能量失衡的問題,基于此問題,本文提出了狹長域無線傳感器網(wǎng)絡(luò)動態(tài)能量均衡控制方法。
無線傳感器網(wǎng)絡(luò)可抽象為由若干個節(jié)點及節(jié)點與節(jié)點之間的連接邊組成,這樣便形成了由節(jié)點集合V和連接邊集合E組成的圖G=(V,E),集合E中每個元素都有集合V中的兩個元素與之對應(yīng)。網(wǎng)絡(luò)中的節(jié)點數(shù)可描述為N=|V|,節(jié)點與節(jié)點之間的連接邊數(shù)可描述為M=|E|。假設(shè)網(wǎng)絡(luò)中連接邊的存在總是意味著一定有兩個能夠互相傳輸數(shù)據(jù)的節(jié)點在邊的兩端,不考慮連接強度,并且兩個節(jié)點之間至多只有一條連接邊,節(jié)點本身不可以自連接,這樣就形成了無方向、無加權(quán)的簡單圖,本文即是基于簡單圖進行討論。簡單圖中與支配集相關(guān)的定義如下描述:
定義1 支配集與連通支配集:若圖G=(V,E)中存在D?V,?u∈VD,在D中至少存在一個節(jié)點與u之間存在連接邊,則集合D為圖G的一個支配集。可以看出,支配集的個數(shù)往往不唯一。若D中的節(jié)點是連通的,則集合D為圖G的一個連通支配集。
定義2 極小支配集:若對于圖G的一個支配集D,其子集均不能成為圖G的支配集,則D為圖G的極小支配集。
定義3 最小支配集:對于圖G中的所有支配集,可以找到包含節(jié)點數(shù)最少的那個支配集,稱之為最小支配集。容易得到,最小支配集一定是一個極小支配集,反之不然。
定義4 獨立集:對于圖G=(V,E)中的一個集合I?V,I中任意兩個節(jié)點都不存在連接邊,則稱集合I為圖G的一個獨立集。
定義5 極大獨立集:對于獨立集I,若存在?v∈VI,使得I與{v}的并集不是獨立集,則稱該獨立集I為極大獨立集。
定義6 最大獨立集:對于圖G中的所有獨立集,可以找到包含節(jié)點數(shù)最多的那個獨立集,稱之為最大獨立集。
定義7 生成樹:對于圖G的一個子圖T,若T是一棵不含閉合路徑的連通樹,且節(jié)點v(T)=v(G),則稱T是G的生成樹。
無線傳感器網(wǎng)絡(luò)中經(jīng)典的基于連通支配集的拓撲構(gòu)造算法有A3[8]、A3 Cov[9]、EECDS[10]和CDS Rule K[11]等。其中,A3和A3 Cov屬于基于增長樹的拓撲構(gòu)造算法;EECDS是基于連通獨立集的拓撲構(gòu)造算法;CDS Rule K是基于剪枝的拓撲構(gòu)造算法。
一個完整的無線傳感器網(wǎng)絡(luò)拓撲控制應(yīng)該包含拓撲構(gòu)造和拓撲維護兩方面[12]。上述拓撲構(gòu)造算法即是在保證網(wǎng)絡(luò)連通和覆蓋的前提下,盡量簡化網(wǎng)絡(luò)結(jié)構(gòu),減少能量消耗。盡管網(wǎng)絡(luò)已經(jīng)簡化,節(jié)點的能耗速度仍然不同。例如,由于所有節(jié)點采集的數(shù)據(jù)都向Sink節(jié)點匯集,那么距離Sink節(jié)點較近的普通節(jié)點自然承擔(dān)著更重的數(shù)據(jù)流量,能耗速度自然更快。拓撲維護的作用就是在原有的拓撲結(jié)構(gòu)即將遭到破壞時(由于某些節(jié)點能量的即將耗盡)轉(zhuǎn)變成一種新的拓撲結(jié)構(gòu),以緩解任務(wù)較重的節(jié)點,達到網(wǎng)絡(luò)負載均衡的目的。正是由于最小連通支配集的不唯一性,為拓撲構(gòu)造和拓撲維護的交替運作提供了理論支持。
2.1 拓撲維護方式及其觸發(fā)條件
拓撲維護可分為靜態(tài)、動態(tài)和混合三種方式。為網(wǎng)絡(luò)設(shè)定一定條件的閾值,靜態(tài)拓撲維護是指在拓撲構(gòu)造時預(yù)先維護不唯一的拓撲結(jié)構(gòu),當(dāng)網(wǎng)絡(luò)運行超過閾值時,根據(jù)預(yù)先維護的、可達到閾值條件的其他拓撲來替代當(dāng)前拓撲;動態(tài)拓撲維護是指網(wǎng)絡(luò)運行的任何時刻,一旦超過閾值,立即終止當(dāng)前拓撲,重新構(gòu)建拓撲結(jié)構(gòu);混合拓撲維護是指網(wǎng)絡(luò)運行超過閾值時,先利用靜態(tài)拓撲維護機制,如果預(yù)先維護的拓撲結(jié)構(gòu)都不能替代當(dāng)前拓撲,則調(diào)用動態(tài)拓撲維護機制來重建拓撲結(jié)構(gòu)。
常見的觸發(fā)拓撲維護的條件如下描述:
隨機拓撲維護:設(shè)定一個隨機數(shù),拓撲維護隨機進行。這種方法可能會給網(wǎng)絡(luò)運行帶來較大不確定性。
基于失效節(jié)點的拓撲維護:當(dāng)網(wǎng)絡(luò)中失效節(jié)點達到一定數(shù)量時進行拓撲重構(gòu)。此方法并沒有盡量避免節(jié)點的能量耗盡,在稀疏性網(wǎng)絡(luò)中可能導(dǎo)致覆蓋率的急劇下降。
基于節(jié)點密度的拓撲維護:當(dāng)網(wǎng)絡(luò)平均節(jié)點度達到一定閾值時進行拓撲重構(gòu)。節(jié)點度描述的是節(jié)點鄰居的個數(shù),平均節(jié)點度是指所有節(jié)點度之和與節(jié)點數(shù)之比。由于節(jié)點度本身需要一定的計算量,此方法可能產(chǎn)生較大的額外開銷。
基于時間閾值的拓撲維護:可以在全網(wǎng)節(jié)點定義一個時間閾值,當(dāng)網(wǎng)絡(luò)運行到閾值時間時,即刻進行拓撲重構(gòu)。此方法的關(guān)鍵在于閾值大小的確定,若閾值過小,拓撲重構(gòu)的次數(shù)就會過多,給網(wǎng)絡(luò)帶來額外的開銷;若閾值過大,可能導(dǎo)致在拓撲重構(gòu)時死亡節(jié)點過多,影響覆蓋率。
基于能量閾值的拓撲維護:對網(wǎng)絡(luò)節(jié)點能量設(shè)定一個閾值,網(wǎng)絡(luò)能量低于此閾值時進行拓撲重構(gòu)。此方法的特點與基于時間閾值的拓撲維護類似。
2.2 基于介數(shù)緩沖的動態(tài)能量均衡拓撲維護
由于靜態(tài)拓撲維護會給網(wǎng)絡(luò)帶來額外開銷,本文將采用動態(tài)拓撲維護機制。節(jié)點能量的均衡利用是無線傳感器網(wǎng)絡(luò)最重要的目標,所以本文采用能量閾值作為拓撲重構(gòu)的觸發(fā)條件。將能量閾值設(shè)定為單個節(jié)點的10%,即當(dāng)某個活動節(jié)點的剩余能量低于其初始能量的10%時,重新調(diào)用拓撲構(gòu)造算法。另外,本文還特別關(guān)注無線傳感器網(wǎng)絡(luò)中的那些注定要消耗更多能量的重要節(jié)點。如前所述的距離Sink節(jié)點較近的普通節(jié)點,由于其位置的重要性,無論怎么重新構(gòu)造拓撲結(jié)構(gòu),這類節(jié)點始終需要包含在活動節(jié)點之中,始終要最先耗盡能量。本文將這種重要節(jié)點抽象成介數(shù)中心性重要節(jié)點,并對之進行數(shù)據(jù)緩沖處理,以延長此類節(jié)點的壽命,從而進一步增加網(wǎng)絡(luò)生命周期。
用經(jīng)過某節(jié)點的最短路徑數(shù)目來刻畫此節(jié)點重要性的指標叫做介數(shù)中心性(Betweenness Centrality, BC)[13]。無線傳感器網(wǎng)絡(luò)節(jié)點i的介數(shù)定義為:
(1)

在不考慮節(jié)點計算能耗的條件下,網(wǎng)絡(luò)節(jié)點能耗主要包含三大部分:發(fā)送信息產(chǎn)生的能耗、接收信息產(chǎn)生的能耗和感知信息產(chǎn)生的能耗。由于網(wǎng)絡(luò)中所有節(jié)點均需要感知信息并發(fā)送出去,且能耗一致,所以介數(shù)中心性重要節(jié)點和普通節(jié)點的能耗區(qū)別在于接收來自其他節(jié)點的信息并發(fā)送出去(轉(zhuǎn)發(fā))的次數(shù)。減少介數(shù)中心性重要節(jié)點對信息轉(zhuǎn)發(fā)的次數(shù),是網(wǎng)絡(luò)能量均衡的有效辦法。一種方案是移動另一節(jié)點到重要節(jié)點處作為支援節(jié)點;另一種方案是重要節(jié)點的鄰居節(jié)點將信息暫存在緩沖區(qū)中進行聚集,緩沖區(qū)滿后再轉(zhuǎn)發(fā)給重要節(jié)點。對于部署在特殊環(huán)境下的無線傳感器網(wǎng)絡(luò)而言,節(jié)點的移動往往較為困難,第二種方案是可行的。
若某節(jié)點的介數(shù)值大于網(wǎng)絡(luò)平均介數(shù)值,即可判定自身為重要節(jié)點,并可將此信息發(fā)送給鄰居節(jié)點。當(dāng)鄰居節(jié)點需要發(fā)送信息給重要節(jié)點時,會采用緩沖并聚集的方法來減少重要節(jié)點的轉(zhuǎn)發(fā)次數(shù),本文將節(jié)點緩沖區(qū)大小設(shè)置為數(shù)據(jù)包長的5倍。此方案在犧牲較少數(shù)據(jù)傳輸延時的情況下,延長了網(wǎng)絡(luò)生命周期。
目前我國對諸如礦井和軌道內(nèi)基礎(chǔ)設(shè)施的檢查仍然主要采用檢查車和人工巡查的方式,這種傳統(tǒng)方式在數(shù)據(jù)的準確性、廣泛性、實時性和節(jié)能等方面都存在較大缺陷[14]。雖然當(dāng)前對橋梁、岔口等特定區(qū)域做了重點監(jiān)測,但尚無面向整個網(wǎng)絡(luò)的監(jiān)測。利用無線傳感器網(wǎng)絡(luò)對基礎(chǔ)設(shè)施進行監(jiān)測,是解決當(dāng)前問題的最佳解決方案。
在狹長區(qū)域部署的無線傳感器網(wǎng)絡(luò)除了要監(jiān)測靜止的基礎(chǔ)設(shè)施之外,還要監(jiān)測區(qū)域內(nèi)的穿過物。物體沿任何路徑穿過該區(qū)域時,都能夠被至少一個節(jié)點探測到的網(wǎng)絡(luò)覆蓋方式被稱為柵欄覆蓋[15-16]。顯然對于同質(zhì)網(wǎng)絡(luò)而言,為了保證柵欄覆蓋,網(wǎng)絡(luò)中節(jié)點數(shù)N必須滿足式(2)所示的條件。其中L為目標區(qū)域長度,rs為節(jié)點感知半徑。
(2)
對于連通性而言,文獻[17]已經(jīng)證明,當(dāng)傳輸半徑rc≥rs,且目標區(qū)域被節(jié)點全覆蓋,就能保證網(wǎng)絡(luò)全連通。
本文采用的網(wǎng)絡(luò)模型為:
1)狹長域無線傳感器網(wǎng)絡(luò)由N個同質(zhì)節(jié)點和1個Sink節(jié)點構(gòu)成,且Sink節(jié)點位于域的中心位置。普通節(jié)點具有一定的初始能量,在數(shù)據(jù)采集、計算、傳輸和轉(zhuǎn)發(fā)過程中均有能量消耗,Sink節(jié)點無能量限制;
2)被監(jiān)測區(qū)域為長度遠大于寬度的狹長帶狀區(qū)域;
3)節(jié)點在被監(jiān)測區(qū)域為隨機布局,且保證欄柵覆蓋和全連通。節(jié)點一旦撒下,其位置固定,不可移動。節(jié)點發(fā)送1bit數(shù)據(jù)所消耗的能量為:ETxbit=Eelect+Eamp·(π·r2);接收1 bit數(shù)據(jù)所消耗的能量為:ERxbit=Eelect。其中r為節(jié)點通信半徑,Eamp為發(fā)送放大器的消耗能量;
4)節(jié)點在網(wǎng)絡(luò)中的編號各不相同,節(jié)點之間的傳輸鏈路無向,且可根據(jù)接收信號的強弱來判斷信息發(fā)送者的遠近。
將基于介數(shù)緩沖的動態(tài)能量均衡拓撲維護機制分別融入到A3、A3 Cov、EECDS和CDS Rule K等拓撲構(gòu)造算法之中(分別命名為:BC-Based A3、BC-Based A3 Cov、BC-Based EECDS和BC-Based CDS Rule K),在1 000 m×100 m狹長帶狀區(qū)域內(nèi)隨機部署200個節(jié)點(節(jié)點分布情況如圖1所示),對算法進行了仿真和對比分析。仿真基于Java平臺,仿
真得到的數(shù)據(jù)在Matlab中進行處理分析。具體仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

圖1 節(jié)點分布圖
Fig.1 Node distribution
本文將生命周期定義為從無線傳感器網(wǎng)絡(luò)運行開始至與Sink節(jié)點存在連接的節(jié)點完全死亡為止。以時間為橫坐標,與Sink存在連接的活動節(jié)點數(shù)目為縱坐標,對比各個協(xié)議的生命周期情況如圖2-圖5所示。可以看出,在沒有添加基于介數(shù)緩沖的動態(tài)能量均衡拓撲維護機制時,A3、A3 Cov、EECDS和CDS Rule K都存在活動節(jié)點數(shù)量階躍式下降的情況。向經(jīng)典協(xié)議添加新機制之后,活動節(jié)點數(shù)的下降趨勢得到了明顯的緩沖,證明新機制下的拓撲控制協(xié)議使網(wǎng)絡(luò)能量得到了很好的均衡控制,整個網(wǎng)絡(luò)的生命周期得到了明顯的改善。
本文提出了狹長域無線傳感器網(wǎng)絡(luò)動態(tài)能量均衡控制方法,該方法將節(jié)點動態(tài)能量均衡的方法融入到經(jīng)典算法之中,采用能量閾值作為拓撲重構(gòu)的觸發(fā)條件,當(dāng)某個活動節(jié)點的剩余能量低于其初始能量的10%時,重新調(diào)用拓撲構(gòu)造算法。另外,本文還分析了介數(shù)中心性節(jié)點對網(wǎng)絡(luò)性能的影響,對介數(shù)中心性重要節(jié)點進行了緩沖管理。在狹長形狀區(qū)域內(nèi)布置隨機網(wǎng)絡(luò),對基于介數(shù)緩沖的動態(tài)能量均衡拓撲控制算法進行了仿真分析。結(jié)果表明,向經(jīng)典協(xié)議添加新機制之后,活動節(jié)點數(shù)的下降趨勢得到了明顯的緩沖,證明新機制下的拓撲控制協(xié)議使網(wǎng)絡(luò)性能得到了明顯的改善。
[1]Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey [J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2008, 52(12):2292-2330.
[2]Chen CP, Mukhopadhyay SC, Chuang CL, et al. Efficient coverage and connectivity preservation with load balance for wireless sensor networks[J]. Sensors Journal IEEE, 2015, 15(1):48-62.
[3]Wang H, Huang Y, Roman HE. Some fundamental results on complex network problem for large-scale wireless sensor networks[J]. Wireless Personal Communications, 2014, 77(77):1-17.
[4]Jelicic V, Magno M, Brunelli D, et al. Benefits of wake-up radio in energy-efficient multimodal surveillance wireless sensor network[J]. IEEE Sensors Journal, 2014, 14(9):3210-3220.
[5]Liu X, Cao J, Tang S, et al. Enabling reliable and network-wide wakeup in wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2015, 4490(1):1-1.
[6]Chen H, Li X, Zhao F. A reinforcement learning-rased sleep scheduling algorithm for desired area coverage in solar-powered wireless sensor networks[J]. IEEE Sensors Journal, 2016, 16(8):2763-2774.
[7]Gorain B, Mandal PS. Line sweep coverage in wireless sensor networks[C]//Sixth International Conference on Communication Systems & Networks, 2014:1-6.
[8]Wightman PM, Labrador MA. A3: A topology construction algorithm for wireless sensor networks[J]. IEEE Globecom IEEE Global Telecommunications Conference, 2008, 48(4):1-6.
[9]Wightman PM, Labrador MA. A3Cov: A new topology construction protocol for connected area coverage in WSN[J]. IEEE Wireless Communications and Networking Conference, 2011, 34(17):522-527.
[10]Zeng Y Y, Xiao H J, He Y X. Energy efficient distributed connected dominating sets construction in wireless sensor networks [C]//International Conference on Wireless Communications & Mobile Computing, 2006:797-802.
[11]Wu J, Cardei M, Dai F, et al. Extended dominating set and its applications in ad hoc networks using cooperative communication[J]. IEEE Transactions on Parallel & Distributed Systems, 2006, 17(8):851-864.
[12]Wightman PM, Labrador MA. Topology maintenance: Extending the lifetime of wireless sensor networks[J]. Latin America Transactions IEEE, 2010, 8(4):469-475.
[13]汪小帆, 李翔, 陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論[M]. 北京:高等教育出版社, 2012: 159-161.
[14]霍宏偉, 郜帥, 牛延超, 等. 一種實時軌道監(jiān)測無線傳感器網(wǎng)絡(luò)與服務(wù)模型研究[J]. 鐵道學(xué)報, 2008, 30(6):51-57.
[15]He SB, Chen JM, Li X, et al. Mobility and intruder prior information improving the barrier coverage of sparse sensor networks[J]. IEEE Transactions on Mobile Computing, 2014, 13(6): 1268-1282.
[16]Tao D, Wu TY. A survey on barrier coverage problem in directional sensor networks[J]. IEEE Sensors Journal, 2015, 15(2): 876-885.
[17]付俊松, 張振江, 劉云. 一種軌道交通新型無線傳感器網(wǎng)絡(luò)能量有效覆蓋算法RTST的研究與仿真[J]. 鐵道學(xué)報, 2014(01):49-55.
TopologyControlforWirelessSensorNetworksBasedonDynamicEnergyBalanceinNarrowRegion
LIU Yan, GENG Peng, YANG Jie
(Nanjing Institute of Technology, Nanjing 211167, China)
The wireless sensor networks topology construction algorithm based on connected dominating set has the problem of energy imbalance in the application of narrow region environment. We proposed a dynamic energy balance control method for narrow region wireless sensor networks. The topology construction algorithms such as A3, A3 CoV, EECDS and CDs rule K were analyzed. We integrated the dynamic energy balance of nodes into these algorithms and the buffer management was used in the betweenness centrality important nodes. The dynamic energy balance topology control algorithm based on the betweenness buffer management was simulated and analyzed in the orbit shape region. The simulation results showed that the new algorithm could make full use of node energy, prolong the network lifetime, and improve the overall performance of the wireless sensor networks.
wireless sensor networks; narrow region; energy balance; betweenness centrality
2017-04-10
南京工程學(xué)院校級科研基金項目資助(QKJA201509);江蘇省自然科學(xué)基金項目資助(BK20160781);江蘇省高校自然科學(xué)研究基金項目資助(16KJB510013)
柳艷(1980—),女,江蘇高郵人,講師,研究方向:應(yīng)用數(shù)學(xué),無線傳感器網(wǎng)絡(luò),復(fù)雜網(wǎng)絡(luò)。E-mail:huayiliu2000@126.com。
TP393
A
1008-1194(2017)05-0076-05