基于時間同步的無線傳感器網(wǎng)絡覆蓋控制優(yōu)化算法

1、收稿日期:2011-04-04;修回日期:2011-07-18基金項目:國家自然科學基金資助項目(6077683460870010作者簡介:常光強(1986-,男,山東濰坊人,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(chgq0307163com ;樊曉平(1961-,男,教授,博導,主要研究方向為智能信息處理、信號處理等;劉少強(1964-,男,副教授,博士,主要研究方向為傳感器及智能檢測技術(shù)、無線傳感器網(wǎng)絡基于時間同步的無線傳感器網(wǎng)絡覆蓋控制優(yōu)化算法*常光強,樊曉平,劉少強(中南大學信息科學與工程學院,長沙410001摘要:為了實現(xiàn)網(wǎng)絡覆蓋控制的優(yōu)化,減少能耗,提出了一種分布的、高效節(jié)能、

2、與節(jié)點位置無關(guān)的傳感器網(wǎng)絡覆蓋算法。在該算法中,節(jié)點與鄰居交換信息,并通過能量大小競選工作節(jié)點,節(jié)點根據(jù)自身與工作節(jié)點的距離判斷決定進入工作狀態(tài)或休眠狀態(tài),并采用在生成樹中廣播時間同步算法使工作節(jié)點網(wǎng)絡達到時間同步。仿真結(jié)果比較表明,該算法能夠明顯減少工作節(jié)點數(shù),從而減少能量消耗,延長網(wǎng)絡壽命。關(guān)鍵詞:無線傳感器網(wǎng)絡;覆蓋問題;與位置無關(guān);覆蓋優(yōu)化中圖分類號:TP393;TP301.6文獻標志碼:A文章編號:1001-3695(201201-0035-03doi :103969/jissn1001-3695201201009Coverage control optimization algor

3、ithm in wireless sensor networks ontime synchronizationCHANG Guang-qiang ,FAN Xiao-ping ,LIU Shao-qiang(College of Information Science Engineering ,Central South University ,Changsha 410001,China Abstract :In order to achieve optimal control of network coverage ,reduce energy consumption ,this paper

4、 presented a distrib-uted ,energy efficient ,and the node position independent of the sensor network coverage algorithmIn the algorithm ,nodes exchanged information with neighbors and worked through the energy of running nodes ,other nodes according to their distance from the node with the work ,mad

5、e judgments ,or to enter the work state ,or into sleep stateSimulation results show that thealgorithm can significantly reduce the number of nodes working ,thus to reduce energy consumption and prolong network life-timeKey words :wireless sensor networks (WSN ;coverage problem ;location-unaware ;cov

6、erage optimization0引言無線傳感器網(wǎng)絡(wireless sensor network ,WSN 的覆蓋控制,就是在傳感器網(wǎng)絡節(jié)點能量、無線網(wǎng)絡通信帶寬、網(wǎng)絡計算處理能力等資源普遍受限的情況下,通過網(wǎng)絡傳感器節(jié)點放置以及路由選擇等手段,最終使無線傳感器網(wǎng)絡的各種資源得到優(yōu)化分配。選擇合適的無線傳感器網(wǎng)絡覆蓋控制策略,有助于網(wǎng)絡節(jié)點能量的有效控制、感知服務質(zhì)量的提高和整體生存時間的延長1 3。作為一種分布式系統(tǒng),WSN 時間同步是至關(guān)重要的。時間同步為建立許多WSN 的應用提供了基礎(chǔ)的服務。例如,傳感器節(jié)點間的協(xié)調(diào)和協(xié)作需要時間同步。傳感器節(jié)點需要在同一時刻休眠和喚醒,否則多個

7、節(jié)點同時進入休眠狀態(tài)會使網(wǎng)絡出現(xiàn)盲區(qū)。近年來已有一些學者開展了WSN 優(yōu)化覆蓋控制方面的研究工作,并取得了一定的進展。Ye 等人4提出了基于探測(probing 的密度控制算法PEAS 。PEAS 算法要求每個睡眠節(jié)點定期地在其探測范圍內(nèi)探測鄰居節(jié)點的狀態(tài),若在其探測范圍內(nèi)沒有工作節(jié)點,則進入工作狀態(tài);否則仍處于睡眠狀態(tài)。顯然,PEAS 算法中的某些節(jié)點可能持續(xù)工作,導致過早死亡,由于網(wǎng)絡中的節(jié)點能耗不均勻?qū)⒂绊懜采w質(zhì)量。Zhang 等人在文獻5中討論了網(wǎng)絡覆蓋和連通性,提出了一種分布式的節(jié)點密度控制算法OGDC ,算法要求節(jié)點根據(jù)其鄰居信息和自己的位置信息計算與鄰居節(jié)點的覆蓋關(guān)系。Xu 等人

8、在文獻6中提出了GAF (geographical adaptive fidelity 算法。在GAF 算法中,每個節(jié)點根據(jù)其位置信息將整個區(qū)域劃分為若干個虛擬單元格(grid ,其大小必須保證相鄰格子中任何一對節(jié)點可以直接通信。但是GAF 算法沒有考慮到實際網(wǎng)絡中節(jié)點之間距離的鄰近并不能代表節(jié)點之間可以直接通信的問題,也不能保證節(jié)點能耗均勻。毛鶯池等人在文獻7中提出了DELIC 協(xié)議,協(xié)議中的節(jié)點與鄰居交換信息,并通過能量大小競選工作節(jié)點,其他未競選成功的節(jié)點關(guān)閉通信設備。目前的大部分覆蓋控制算法都需要節(jié)點的精確位置信息以計算節(jié)點間的覆蓋關(guān)系,在選取活動過程中產(chǎn)生較大的計算和控制開銷。本文主

9、要研究了時間同步以及與位置無關(guān)的無線傳感器網(wǎng)絡優(yōu)化覆蓋控制策略,無須節(jié)點的位置信息,從而減少了整個網(wǎng)絡額外的能量消耗。1網(wǎng)絡模型的建立和問題陳述1.1網(wǎng)絡模型的建立假設N 個傳感器節(jié)點隨機均勻地部署在一個L L 的二維正方形區(qū)域M 內(nèi),節(jié)點密度要求足夠大,當所有傳感器節(jié)點都處于工作狀態(tài)時,能夠?qū)φ麄€區(qū)域完全覆蓋且整個網(wǎng)絡是連第29卷第1期2012年1月計算機應用研究Application Research of Computers Vol.29No.1Jan.2012通的,并假設該無線傳感器網(wǎng)絡具有以下性質(zhì):a 節(jié)點部署方式。節(jié)點是同構(gòu)的,節(jié)點采用隨機部署,且部署后節(jié)點不能移動。b 節(jié)點通信范

10、圍。相對于節(jié)點感知范圍而言,監(jiān)測區(qū)域M 足夠大(Rs L ,邊界因素可以忽略。c 節(jié)點感知模型。節(jié)點采用布爾感知模型,即每個節(jié)點的感知范圍是以節(jié)點為圓心、傳感半徑Rs 為半徑的圓,在感知范圍內(nèi)的所有節(jié)點都可以被感知,否則不被感知。d 節(jié)點位置信息。每個節(jié)點無須裝備GPS ,且不能通過測量或定位方法獲得其具體的物理位置。1.2問題陳述無線傳感器網(wǎng)絡覆蓋控制優(yōu)化的主要目的是調(diào)度節(jié)點的休眠間隔時間,滿足覆蓋要求下保持部分節(jié)點為工作狀態(tài),但網(wǎng)絡仍能提供連續(xù)的檢測服務。服務質(zhì)量期望值q (desired QoS 表示了網(wǎng)絡覆蓋率。為所有工作節(jié)點構(gòu)成的監(jiān)測區(qū)域面積占整個區(qū)域M 面積的比例,即:q =(ki

11、 =1SR i M areaM area。假設在監(jiān)測區(qū)域M 中隨機均勻部署N 個節(jié)點,每個節(jié)點S i (1i N 的監(jiān)測范圍為SR i ,需要從N 個節(jié)點中最少選取多少個工作節(jié)點,使得這些工作節(jié)點能夠滿足應用期望的服務質(zhì)量(其中K 是最少選取的工作節(jié)點數(shù)量,即:(ki =1SR i M areaM areaq ,以及如何選取K 個工作節(jié)點。工作節(jié)點的選取應考慮節(jié)點的能量大小。由于在每輪中節(jié)點的能量開銷不一致,需要算法保證能量開銷被均勻地分布到每個節(jié)點上,避免某些節(jié)點過早死亡。如果網(wǎng)絡中的節(jié)點時間不同步也會對覆蓋強度造成影響,假設節(jié)點時鐘與標準時鐘差在區(qū)間(T /2,T /2上均勻分布,即t U

12、 (T /2,T /2,當節(jié)點分布滿足Poisson 點過程時,網(wǎng)絡覆蓋強度8為C n '=C n 2k M exp (M 2k exp (M k exp (M k其中:M 表示區(qū)域M 的面積,表示Poisson 點過程強度。2算法描述2.1工作節(jié)點選取機制算法中傳感器節(jié)點共有四種狀態(tài):準備狀態(tài)(ready 、工作狀態(tài)(active 、偵聽狀態(tài)(listening 、休眠狀態(tài)(sleep 。節(jié)點狀態(tài)轉(zhuǎn)換如圖1所示 。在算法每輪開始時,所有節(jié)點都處于準備狀態(tài)(ready ,首先,從所有節(jié)點中隨機選取一個根節(jié)點進入工作狀態(tài)。首個節(jié)點的隨機選擇機制:計算自己此輪中被選中的閾值T (n ,與文

13、獻9選取簇頭的機制類似,閾值大于事先設定值則選為工作節(jié)點。T (n =P work1P work Round mod ?1P work E curr E max+Round s div ?1P work1E currE max其中:P work 為被選作工作節(jié)點的概率,即P work =K /N ;Round 為算法運行的輪數(shù);Round s 表示節(jié)點連續(xù)沒有被選為工作節(jié)點的輪數(shù),當節(jié)點成為工作節(jié)點后,Round s 重置為0。在這個模型中,每一個節(jié)點通過由自身內(nèi)部的晶體振蕩器提供的本地計時器記錄自己的時間。根節(jié)點是所有節(jié)點中選出來的可以作為時間基準的節(jié)點。這個節(jié)點可以訪問外部時鐘并能夠與物理

14、時鐘達到同步,根節(jié)點層號為0。同時工作節(jié)點向其鄰居節(jié)點廣播自身信息(self-message ,SM 。SM 信息包括節(jié)點ID 信息、status 和層號。收到SM 信息的節(jié)點檢測與active 節(jié)點之間的距離。若0d Rs ,為了使整個網(wǎng)絡的能耗均衡,避免個別傳感器節(jié)點提前死亡,傳感器節(jié)點由ready 狀態(tài)以概率P active =P init E current /E max 轉(zhuǎn)為偵聽狀態(tài),成為偵聽節(jié)點。其中,P init 為工作節(jié)點的初始概率。若Rs d 2Rs ,則傳感器節(jié)點由ready 狀態(tài)轉(zhuǎn)為active 狀態(tài)。為了避免在這一輪中有過多的鄰居節(jié)點被選為工作節(jié)點,在此引入避讓(bac

15、k-off 機制,分別為每個開始節(jié)點設置一個隨機時間T d 。若節(jié)點在T d 時間內(nèi)沒有收到其他開始節(jié)點的SM 信息,則將自身狀態(tài)激活為active 狀態(tài),并向其鄰居節(jié)點發(fā)送SM 信息;若在T d 時間內(nèi)又收到其他鄰居節(jié)點的SM 信息,則取消隨機時間,并再次判斷與此開始節(jié)點的距離。若d Rs 則進入listening 狀態(tài);若d Rs 則進入active 狀態(tài),并向其鄰居節(jié)點發(fā)送SM 信息。每一個根節(jié)點臨近的鄰居節(jié)點收到SM 信息后,它們就知道父節(jié)點的標志符和層號。接著,記錄下標志符,給自己設置一個比父節(jié)點層號大1的層號,然后給根節(jié)點發(fā)送一個反饋信息,表明它們已經(jīng)加入根節(jié)點。同理,其他節(jié)點根據(jù)

16、上述條件決定自身的狀態(tài)和層號,它們鄰近的鄰居將得到SM 信息并加入生成樹。這個過程一直進行,直到WSN 中所有的節(jié)點都加入到生成樹為止。然而一個已經(jīng)加入到生成樹的節(jié)點還有可能再一次接收到其他的SM 信息,如果有這種情況,若處于lis-tening 狀態(tài)下的節(jié)點收到SM 信息后,鄰居節(jié)點中工作節(jié)點數(shù)加1,層號信息不變。圖2展示了生成樹的結(jié)果。當步驟1結(jié)束時,所有的節(jié)點處于active 或listening 狀態(tài)。Listening 狀態(tài)節(jié)點檢測其d Rs 范圍內(nèi)有無工作節(jié)點,若沒有則將自身激活為active 狀態(tài);若Rs 范圍內(nèi)有工作節(jié)點,則其工作狀態(tài)不變,等待進一步的判斷。直到所有傳感器的感知

17、范圍內(nèi)有一個工作節(jié)點或本身是一個工作節(jié)點,層號以及根節(jié)點信息不變。為了滿足網(wǎng)絡的覆蓋要求,需要進一步從listening 節(jié)點中選取節(jié)點進入active 狀態(tài)。根據(jù)現(xiàn)有的節(jié)點冗余度數(shù)學模型10,對節(jié)點分布進行進一步選取,當鄰居節(jié)點數(shù)量大于閾值時,說明節(jié)點為冗余節(jié)點,可以關(guān)閉通信設備,進入sleep 狀態(tài);否則節(jié)點成為工作節(jié)點,保證網(wǎng)絡的覆蓋率,閾值的大小與應用期望的服務質(zhì)量q 有關(guān)。為避免多個節(jié)點同時進入工作狀態(tài),同理可引入避讓(back-off 機制。·63·計算機應用研究第29卷當整個傳感器網(wǎng)絡中的節(jié)點通過以上算法達到確定狀態(tài)(進入休眠狀態(tài)或工作狀態(tài)之后,將在T w 時

18、間內(nèi)保持整個狀態(tài)不變,經(jīng)過T w 后,所有節(jié)點被重新喚醒,所有傳感器節(jié)點重新在下一輪的鄰居節(jié)點集建立和工作節(jié)點的選取。2.2在生成樹中的廣播時間同步算法在生成樹建立起來后,整個WSN 已經(jīng)被分為幾個可以看到的子樹,如圖3所示 。具有精確外部時鐘的根節(jié)點將同步它的子樹根節(jié)點1、2和3。在1、2、3重置它們的時間為標準時間后,它們會同步其子樹的節(jié)點。這種子樹時鐘同步過程會持續(xù)下去,直到所有節(jié)點設定與根節(jié)點一樣的時鐘為止。每次的子樹同步過程如圖4所示 。每個節(jié)點時鐘都不相同,因此每兩個節(jié)點間都會有時間偏差,而只有根節(jié)點具有標準的時間。起初根節(jié)點向它的子樹節(jié)點1、2、3廣播一個同步包,假如這個同步包包

19、含節(jié)點1的標志符,這意味著根節(jié)點選擇節(jié)點1來進行一對同步,因此稱節(jié)點1為消息節(jié)點。假設根節(jié)點的子節(jié)點會在同一時刻接收到同步信息包。在節(jié)點1接收到同步包后,它知道了包中的標志符與它自己的一樣,節(jié)點1記錄接收時間t 2,node1,然后開始處理這個包。在很短的時間后,在節(jié)點1給根節(jié)點發(fā)送返回包之前,記錄瞬時時間t 3,node1,并且把t 2,node1和t 3,node1的信息嵌入到返回包中。當根節(jié)點接收到這個信息時也記錄時間t 4。于是根節(jié)點可以計算出與節(jié)點1的時間偏差如下:O R ,node1=(t 2,node1t 1(t 4t 3,node1/2(1其中:O R ,node1表示了時間偏

20、差。最后根節(jié)點再次廣播一個包含與節(jié)點1的偏差和節(jié)點1的時間信息t 2,node 1的包。當然節(jié)點1基于偏差O R ,node1就能夠調(diào)整自己的時鐘了。另外的節(jié)點利用這個數(shù)據(jù)包信息也可以知道它們與根節(jié)點的偏差。例如,對于節(jié)點2,有t 2,root +O R ,node1=t 2,node1+O node1,node2(2其中:O node1,node2表示節(jié)點1與2的時間偏差。于是可以得到O R ,node2=O R ,node1(t 2,node1t 2,node2(3因為節(jié)點2會接收包括t 2,node1和O R ,node2的廣播包,同時,節(jié)點2也記錄了時間信息t 2,node2,于是O

21、r ,node2可以通過式(3計算得到。在節(jié)點2知道了O R ,Node2后,它將調(diào)整自己的時鐘與根節(jié)點達到同步。余下的節(jié)點如節(jié)點3可以通過同樣的方式與根節(jié)點達到同步11。當子樹中的所有子節(jié)點都與父節(jié)點同步之后,子樹的同步就實現(xiàn)了。很明顯,與根節(jié)點同步的節(jié)點1、2和3也可以被看做它們子樹的父節(jié)點。因此,類似的子樹時間同步過程一直進行,直到整個WSN 都同步到根節(jié)點。3仿真結(jié)果與評價為了驗證該算法選出的工作節(jié)點分布是否良好,在50m 50m 區(qū)域中,隨機部署100 1000個節(jié)點,應用服務期望q =99%,Rs =10m ,Rc =20m 。節(jié)點分布情況如圖5、6中圓點所示,圖中圓盤代表工作節(jié)點

22、的覆蓋范圍。實驗結(jié)果表明,運行該算法后,每輪生成的工作節(jié)點在網(wǎng)絡中分布良好,所選擇的工作節(jié)點完全能夠滿足應用服務期望,而且工作節(jié)點數(shù)相對較少,同時達到了整個網(wǎng)絡工作節(jié)點的時間同步,增強了信息的可靠性。圖7為部署500個節(jié)點時對應的連通效果,可以清晰地看出,整個工作狀態(tài)的節(jié)點組成的網(wǎng)絡是連通的,算法保證了在Rc 2Rs 時整個網(wǎng)絡的連通性。通過在生成樹中廣播時間同步算法,能夠使工作節(jié)點網(wǎng)絡同步到微秒級,在退避時間T d 的允許范圍,因而也消除了網(wǎng)絡中時間異步對覆蓋強度的影響。圖8為在50m 50m 監(jiān)測區(qū)域下與OGDC 、PEAS 、GAF 、DELIC 幾種算法所選擇的工作節(jié)點數(shù)的比較。圖中工

23、作節(jié)點數(shù)為每種算法連續(xù)仿真100次后取平均值所得 。由于本文首先選擇出覆蓋冗余較少的節(jié)點作為整個網(wǎng)絡的支撐節(jié)點,然后又引入節(jié)點冗余度數(shù)學模型選擇節(jié)點,使整個網(wǎng)絡滿足覆蓋要求,所以工作節(jié)點相對較少。從圖中也可以看出,在大多數(shù)情況下DELIC 需要23個工作節(jié)點才能達到99%以上的覆蓋率,對于GAF 協(xié)議,需要的工作節(jié)點數(shù)量幾乎是該算法的2倍多;PEAS 可以提供與該算法差不多的覆蓋質(zhì)量,但是選出的工作節(jié)點數(shù)量比該算法多50%左右;OGDC 節(jié)點數(shù)最少,覆蓋率相對較低,而且OGDC 需要利用節(jié)點的位置信息來控制工作節(jié)點密度。本文算法無須預先得知節(jié)點的位置信息,選擇的工作節(jié)點數(shù)目也相對較少,而且隨著

24、部署節(jié)點的增加,工作節(jié)點數(shù)基本不變。(下轉(zhuǎn)第42頁·73·第1期常光強,等:基于時間同步的無線傳感器網(wǎng)絡覆蓋控制優(yōu)化算法了三種模型。運用模糊模擬與遺傳算法相結(jié)合,設計了一種混合智能算法求解所提出的三個模型。最后,通過一個數(shù)值實驗驗證了混合智能算法的有效性。表4不同參數(shù)設定下的求得的-權(quán)值種群規(guī)模模糊模擬次數(shù)P c P m b p-權(quán)值相對誤差/%10030000501608263823010030000702608263927003910030000501100526411101091003000080112052640840099100500008031208264678

25、0324100500007021003264794036810050000504605264691032950300008041203264221015150300007038082642440160參考文獻:1BAR-YEHUDA R,EVEN SA local-ratio theorem for approximatingthe weighted vertex cover problemJAnnals of Discrete Mathe-matics,1985,109(25:27-452CHVATAL VA greedy-heuristic for the set cover proble

26、mJMathematics of Operations Research,1979,4(3:233-2353DINUR I,SAFRA SThe importance of being biasedC/Proc ofthe34th Annual ACM Symposium on Theory of ComputingNewYork:ACM Press,2002:33-424MONIEN B,SPECKENMEYER ERamsey numbers and an approxi-mation algorithm for the vertex cover problemJActa Informat

27、ica, 1985,22(1:115-1235CHLEBIKA M,CHLEBIKOVA JCrown reductions for the minimumweighted vertex cover problemJDiscrete Applied Mathematics,2008,156(3:292-3126KHOTA S,REGEV OVertex cover might be hard to approximate towithin2-epsilonJJournal of Computer and System Sciences, 2008,74(3:335-3497KARAKOSTAS

28、 GA better approximation ratio for the vertex coverproblemJACM Trans on Algorithms,2009,5(4:1-88NI Yao-dongStochastic minimum weight vertex cover problemC/Proc of the5th International Conference on Information and Manage-ment Sciences2006:358-3649ZADEH L AFuzzy setsJInformation and Control,1965,8(3:

29、338-35310KAUFMANN AIntroduction to the theory of fuzzy subsetsMNewYork:Academic Press,197511NAHMIAS SFuzzy variablesJFuzzy Sets and Systems,1978,1(2:97-11012LIU Bao-dingUncertainty theory:an introduction to its axiomaticfoundationsMBerlin:Springer-Verlag,200413LIU Bao-ding,LIU Y KExpected value of f

30、uzzy variable and fuzzyexpected value modelsJIEEE Trans on Fuzzy Systems,2002, 10(4:445-45014LIU Bao-ding,IWAMURA KChance constrained programming withfuzzy parametersJFuzzy Sets and Systems,1998,94(2:227-23715HOLLAND JAdaptation in natural and artificial systemMAnnArbor,MI:University of Michigan Pre

31、ss,197516KARP R MReducibility among combinatorial problemsC/Procof Complexity of Computer ComputationNew York:Plenum Press, 1972:85-103(上接第37頁4結(jié)束語本文立足于WSN的覆蓋控制問題提出了一個分布的、高效節(jié)能、與節(jié)點位置無關(guān)、基于時間同步的傳感器網(wǎng)絡覆蓋算法。在本文算法的工作節(jié)點選取機制中,節(jié)點通過鄰居節(jié)點的工作狀態(tài)決定自身工作狀態(tài),工作節(jié)點網(wǎng)絡可達到時間同步,根據(jù)能量的大小來選擇工作節(jié)點。模擬實驗結(jié)果表明,在無須節(jié)點位置信息的前提下,該算法能夠大大地減少

32、網(wǎng)絡中的工作節(jié)點數(shù),從而在減少整體能量消耗、均衡節(jié)點能耗方面具有良好的性能。參考文獻:1石為人,袁久銀,雷璐寧無線傳感器網(wǎng)絡覆蓋控制算法研究J自動化學報,2009,35(5:540-5452REN Yan,ZHANG Si-dong,ZHANG Hong-keTheories and algo-rithms of coverage control for wireless sensor networksJJournal ofSoftware,2006,17(3:422-4333WU Yong-an,LI Min,CAI Zhi-ping,et alA distributed algorithm

33、 toapproximate node-weighted minimum a-connected(,k-coverage indense sensor networksC/Proc of International Frontiers of Algo-rithmic Workshop2008:221-2324YE Fan,ZHONG G,LU Song-wu,et alPEAS:a robust energy con-serving protocol for long-lived sensor networksC/Proc of the23rdInternational Conference on Distributed Computing Systems2003:28-3