WSNs中一種尋找最小工作節點集的覆蓋算法

王愛民,劉永強,張 婧,劉衍珩

(1.吉林大學計算機科學與技術學院,吉林長春 130012; 2.吉林大學符號計算與知識工程教育部重點實驗室,吉林長春 130012)

WSNs中一種尋找最小工作節點集的覆蓋算法

王愛民1,2,劉永強1,張 婧1,劉衍珩1,2

(1.吉林大學計算機科學與技術學院,吉林長春 130012; 2.吉林大學符號計算與知識工程教育部重點實驗室,吉林長春 130012)

針對現有覆蓋算法存在的很多冗余節點,提出了尋找最小工作節點集的覆蓋算法.該算法分為兩個階段:第1階段運行已有的覆蓋算法;第2階段運行節點替換算法,它用更少的節點替換更多的工作節點,如此循環迭代使工作節點數不斷減少.仿真實驗表明,該算法比其他覆蓋算法能獲得更多的休眠節點,使工作節點數減少10%左右,從而延長了網絡生命周期.

無線傳感器網絡;覆蓋;睡眠調度算法;休眠順序

傳感器技術、微機電系統、現代網絡和無線通信等技術的進步,推動了無線傳感器網絡的產生和發展.無線傳感器網絡能應用于軍事國防、環境監測、醫療護理和危險區域遠程控制等諸多領域[1-2],在大多數應用場景中節點都是隨機部署的,這樣會導致部署的節點數遠大于所需的節點數,當這些節點都工作時,將會存在大量的冗余節點,如果不對這些節點進行休眠調度,不僅增加了整體能量的消耗,還增加了數據的沖突.為此,人們已經在這方面進行了大量的研究[3-12].文獻[6]提出的算法把區域劃分成方格,1個方格只有1個節點工作,該算法并沒有考慮到網絡覆蓋的問題.文獻[7]提出了滿足覆蓋的休眠調度的Ottawa算法,該算法通過扇形來計算鄰居節點對1個節點的覆蓋,由于只考慮了節點感知區域內的鄰居節點,所以該算法并沒有判斷出所有的冗余節點.文獻[8]改進了文獻[7]提出的算法,對覆蓋進行了更精確的計算.文獻[9]提出了覆蓋配置協議(Coverage Configuration Protocol,CCP)算法,該算法判斷冗余節點的方法是通過判斷節點感知區域內所有交點的覆蓋度是否都大于K.該算法在部署節點較多時不會產生盲點.文獻[10]提出的算法對周邊界覆蓋給出了充要條件,得出更精確的結果.文獻[11]提出的算法,首先基于歐拉距離選出能全覆蓋整個監測區域的節點集,然后選擇離每個節點最近的K-1個節點來滿足K覆蓋.文獻[12]提出了基于虛擬正方形網格的覆蓋算法(Virtual Square Grid-based Coverage Algorithm,VSGCA),該算法把每個節點的感知區域劃分成小方格,然后計算每個鄰居節點對這些小方格的覆蓋.該算法雖然在休眠節點數上沒有文獻[9]提出的算法好,但是它的復雜度比文獻[9]提出的算法低很多.

1　網絡模型和問題描述

1.1假設及定義

下面給出一些假設和定義.假設若干同構節點隨機部署在L×W的區域A,節點的感知模型和通信模型都是圓形,且感知半徑R與通信半徑Rc滿足Rc≥2R(這樣在滿足覆蓋的同時也滿足連通[9]).

定義1 部署在區域A中的節點集合稱為節點集,即S={u1(x1,y1),u2(x2,y2),u3(x3,y3),…,uk(xk, yk),…}.

定義2 節點ui(xi,yi)的感知區域為點的集合,即D(ui)={p(x,y)∈A|(x-xi)2+(yyi)2≤R2}.

定義3 節點ui的鄰居節點集,即N(ui)={uj∈S|(xj-xi)2+(yj-yi)2≤

定義4 假休眠狀態節點指一個節點不執行監測任務,但是能接收和發送消息,預休眠狀態和預工作狀態是狀態轉換中的兩個臨時狀態,表示準備休眠和工作的節點,它們都能接收和發送消息.預休眠狀態是從工作狀態轉換過來的,而預工作狀態是從假休眠狀態轉換過來的.

1.2問題描述

上文介紹的覆蓋算法都能使大部分節點休眠,但是節點感知區域之間仍存在很多重疊區域,它們的平均覆蓋度都大于等于2.觀察其運行結果,有些點的覆蓋度為1,有些點為2,有些點為3,甚至更大.有些區域1個節點就可以覆蓋,但是它們卻用了兩個或者更多的節點覆蓋,而且對相同的網絡拓撲,每次運行生成的工作節點個數都不一樣,且差距很大.

假設在監測區域中有一子區域如圖1所示,子區域A1,傳感器節點集S1(包括所有部署在區域邊界的邊界節點,部署在區域中心的傳感器節點a,以及區域內其他兩個傳感器節點b和c).要滿足子區域A1的全覆蓋,有兩種覆蓋方案:①全部的邊界節點及節點b和c;②全部的邊界節點及節點a.第1種方案比第2種方案的工作節點個數多1.由此可知,工作節點個數與節點的休眠順序有關.若a節點先休眠,則b和c不能休眠;若b或者c先休眠,則a節點不能休眠.當監測區域非常大,且部署節點非常多時,每次生成的工作節點個數都不一樣,且差距很大.文中提出的覆蓋算法解決了上述情況,使得每次運行結果一樣,并且得到的工作節點個數也是最少的,工作節點個數能減少10%,且隨著監測區域的擴大和部署節點的增多,工作節點的個數減少得會越多.文中算法運行于圖1拓撲結構,得到的工作節點為所有的邊界節點和節點a.

圖1　節點部署圖

圖2　理想的節點部署圖

2　與休眠順序無關的覆蓋算法

2.1討 論

這里給出一種比較理想的節點部署情況.如圖2所示.4個圓(半徑為感知半徑的大小為R)相交于一點,節點之間重疊的區域非常少,每個節點的覆蓋范圍可看做是一個正方形,邊長為21/2R,這些節點的位置可表示為

定義5 若一個位置p(x,y)屬于C集合,則稱該點為最佳位置.

2.2算法描述

該算法由兩個階段組成,第1階段是運行已有的覆蓋算法,獲得工作節點集;第2階段是對第1階段獲得的工作節點集進行優化處理,用更少的工作節點集替換它們.

2.2.1第1階段

該階段得到初始的工作節點集,可使用已提出的算法,由于CCP算法能得到較少的工作節點,故使用CCP作為第1階段算法.在運行該算法時,所有應該休眠的節點都進入假休眠狀態,在第2階段這些節點就能發送消息,并且能接收其他節點發送的消息.這樣當第1階段結束時,所有的節點只有兩種狀態:工作狀態或假休眠狀態.

2.2.2第2階段

第2階段算法思想是先讓一個假休眠節點ui為暫時的工作節點,然后計算有多少個工作節點可以休眠,若可以休眠的工作節點個數大于1,則讓該假休眠節點成為工作節點,可以休眠的工作節點成為休眠節點.若可以休眠的工作節點個數等于1,且該假休眠節點ui比可以休眠的工作節點更接近最佳位置(定義5),則讓該假休眠節點成為工作節點,可以休眠的工作節點成為休眠節點;否則,不讓假休眠節點ui成為工作節點.

第2階段的詳細過程如下:

(1)開始時,為避免消息發送沖突,每個假休眠節點ui都等待一段隨機時間;然后,發送測試消息,并修改自己的狀態為預工作狀態,同時設定一個定時器.

(2)工作節點收到該消息時,先判斷自己是否已經收到其他假休眠節點發送的測試消息,如果收到,則拋棄該消息;否則,跳轉到下一步.其他狀態的節點接收到該消息都拋棄.

(3)保存發送節點ui的身份標識號碼(IDentity,ID),在鄰居狀態表中把該鄰居節點ui的狀態改為預工作狀態,然后運行CCP覆蓋算法,若運行結果為非冗余節點,則不進行任何處理;若為冗余節點,則修改自己的狀態為預休眠狀態,并向節點ui發送預休眠消息,表示自己可以休眠,然后跳轉到下一步.

(4)當一個預工作節點ui(即剛才發送測試消息的節點)收到預休眠消息時,首先判斷該消息是否是發送給自己的,若是,則記錄該預休眠消息;若不是,則拋棄.循環處理這一步直到節點的定時器超時,然后轉到下一步.

(5)預工作節點ui計算接收到的預休眠消息的個數為n,若n≥2,則轉步驟(6)處理;若n=1,設發送預休眠消息的節點為uj,則判斷自己ui和節點uj哪一個更接近最佳位置(定義5表示的);若ui更接近,則轉步驟(6)處理;否則,轉步驟(7)處理;若n=0,則轉步驟(7)處理.

(6)預工作節點ui向鄰居節點廣播確認消息,表示此次測試成功,修改自己的狀態為工作狀態,然后轉到步驟(8).

(7)預工作節點ui向鄰居節點廣播取消消息,表示此次測試失敗,把自己的狀態修改回假休眠狀態,然后轉到步驟(8).

(8)當一個預休眠或工作節點收到確認消息時,首先判斷發送該消息的節點ID是否是自己記錄的節點ID,若不是,則不進行處理;若是,則判斷自己的狀態,若為工作狀態,則不進行處理;若為預休眠狀態,則修改自己的狀態為假休眠狀態,并告知鄰居節點自己的狀態.若一個預休眠或工作節點收到取消消息時,同樣先判斷發送該消息的節點是否是自己記錄的節點,若不是,則不進行處理;若是,則判斷自己的狀態;若為工作狀態,不進行處理;若為預休眠狀態,則修改自己的狀態為工作狀態,并告知鄰居節點自己的狀態.

(9)至此,1次迭代過程完成,在一段時間后,則繼續以上步驟迭代,如此循環,直到所指定的時間為止.最后把所有的假休眠節點的狀態改為休眠狀態,整個算法結束.

在步驟(3)中,如果兩個鄰居節點同時判斷為冗余節點,并且讓這兩個節點休眠,則有可能產生盲點.因為每個節點在進行冗余判斷時都假設對方是工作節點.為解決這個問題,需在步驟(3)引入回退機制.該回退機制與CCP算法的回退機制相同.

2.3狀態轉換

圖3只列出了算法第2階段出現的狀態,第1階段結束后節點只有兩種狀態:工作狀態和假休眠狀態.在第2階段節點的狀態有工作狀態、假休眠狀態、預工作狀態、預休眠狀態和休眠狀態.當算法結束時,節點只有兩種狀態:工作狀態和休眠狀態.狀態轉換如圖3所示.

圖3　狀態轉換

2.4時間復雜度

文中算法是由兩階段組成的,第1階段運行CCP算法,第2階段運行節點替換算法.CCP算法的時間復雜度為O(n3)(n表示感知區域內的鄰居節點數)[9].在第2階段,對于工作節點,當它接收測試消息時,使用CCP算法判斷自己是否為冗余節點,由于此時網絡中的平均覆蓋度為一個常數,與初始部署節點數無關.所以,在節點的感知半徑不變的情況下,工作節點的鄰居工作節點數也為常數,因此,1次冗余判斷的時間復雜度為O(1).又由于它有n個鄰居節點,需要判斷n次,故工作節點在第2階段的時間復雜度為O(n),而假休眠節點在第2階段只是對接收信息的判斷及變量的設置,所以它的時間復雜度為O(n),故文中算法的時間復雜度為O(n3)).

3　實驗結果及分析

這里使用仿真實驗實現提出的無線傳感網尋找最小工作節點集(Finding the Minimum working sets in Wireless Sensor networks,FMWS)算法,并與其他算法(Ottawa算法、CCP算法和VSGCA算法)在工作節點數、覆蓋度和是否有盲點等方面進行比較.實驗中,假設監測區域是150 m×150 m的矩形區域,節點的感知半徑為10 m,傳輸半徑為20 m.

3.1盲 點

衡量區域覆蓋算法一個主要的指標是該算法是否產生盲點.由于在文中算法的第2階段步驟(3)和步驟

(4)使用CCP算法來判斷節點是否為冗余節點,當部署節點很多時,CCP算法不產生盲點,所以當部署節點比較多時,文中提出的算法也不會產生盲點.在圖4中,比較了不同算法產生的盲點數.隨著部署節點的增加,盲點個數越來越少,當部署節點數到達一定個數時,所有算法都不產生盲點.

圖4　算法的盲點數比較曲線圖

3.2工作節點

由于工作節點數與網絡生命期成反相關關系,在滿足覆蓋的情況下,工作的節點數越少,網絡生命期越長,故工作節點數能很好反映網絡生命期.在圖5中顯示了工作節點數與部署節點數的關系,該實驗要求的覆蓋度為1,可看出,文中算法生成的工作節點數比其他算法的都要少,其中,Ottawa算法產生的工作節點數大概是其他算法的3倍多,而且隨著部署節點數的增多,工作節點數不斷增多,而其他算法產生的工作節點數保持在一定范圍不變.觀察文中算法產生的工作節點數可知,隨著部署節點不斷增多,工作節點數則不斷減少.為更精確地比較文中算法與CCP算法生成的工作節點數,表1顯示了這兩個算法產生的工作節點個數.從表1可知,文中算法產生的工作節點數比CCP算法大概少10%左右,而且隨著部署節點個數的增加,文中算法產生的工作節點數不斷減少.分析文中算法可知,部署節點越多,在最佳位置的節點越多,生成的工作節點感知區域重疊越少,所以工作節點數就越少.當部署節點無限多時,文中算法產生的節點數則達到圖2所示的比較理想的情況.

3.3平均覆蓋度

圖6比較了各算法的平均覆蓋度.顯示了在部署節點個數不同情況下各算法的平均覆蓋度,部署節點個數從350依次遞增到800.除Ottawa算法的平均覆蓋度在不斷增長外,其他算法的平均覆蓋度在2.0左右.還能看到,文中算法的平均覆蓋度在不同的部署節點下都比其他算法要低,并且隨著部署節點的不斷增多,平均覆蓋度在不斷減小.當部署節點很多時,文中算法要優于其他算法.

表1　工作節點

圖5　算法的工作節點數比較曲線圖

圖6　算法的平均覆蓋度比較曲線圖

4　結束語

筆者提出了尋找最小工作節點集的覆蓋算法,該算法包括兩階段:第1階段可以運行任一覆蓋算法,文中選擇CCP算法作為第1階段運行的算法,在第1階段運行完以后節點只有兩種狀態:工作節點狀態和假休眠節點狀態.在第2階段對工作節點進行替換,它通過循環迭代使工作節點數不斷減少.這樣文中算法得到的工作節點數不比第1階段工作節點數多.由實驗可知,文中算法在工作節點數及平均覆蓋度方面都要優于其他算法,且隨著部署節點的增多,工作節點及平均覆蓋度在不斷趨近于理想情況.雖然文中算法能得到更少的工作節點數,但是還沒有達到最理想情況,特別是在部署節點少的情況下.下一步將對該覆蓋算法作進一步的研究,提出一個在部署節點不是很多的情況下能產生更少工作節點數的算法,讓更多的節點休眠,最大限度地延長網絡生命周期.

[1]ALI R A,HOSSEIN Y M,MASOUD R A.Optimized Congestion Management Protocol for Healthcare Wireless Sensor Networks[J].Wireless Personal Communications,2014,75(1):11-34.

[2]GHASEMIGOL M,GHAEMI-BAFGHI A,YAGHMAEE-MOGHADDAM M H,et al.Anomaly Detection and Foresight Response Strategy for Wireless Sensor Networks[J].Wireless Networks,2015,21(5):1425-1442.

[3]ANJU S,PAL S R.Survey on Coverage Problems in Wireless Sensor Networks[J].Wireless Personal Communications,2015,80(4):1475-1500.

[4]齊小剛,陸贊贊,鄭耿忠,等.一種低能耗低時延的睡眠調度算法[J].西安電子科技大學學報,2015,42(1): 124-129. QI Xiaogan,LU Zanzan,ZHENG Gengzhong,et al.Low-power and Low-delay Sheep Scheduling Algorithm Based on the Data Aggregation Tree[J].Journal of Xidian University,2015,42(1):124-129.

[5]KHAN J A,QURESHI H K,IQBAL A.Energy Management in Wireless Sensor Networks:a Survey[J].Computers &Electrical Engineering,2015,41:159-176.

[6]XU Y,HEIDEMANN J,ESTRIN D.Geography-informed Energy Conservation for Ad Hoc Routing[C]//Proceedings of the Annual International Conferece on Mobile Computing and Networking.New York:ACM,2001:70-84.

[7]TIAN D,GEORGANAS N D.A Coverage-preserving Node Scheduling Scheme for Large Wireless Sensor Networks [C]//Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications.New York:ACM,2002:32-41.

[8]BOUKERCHE A,FEI X,ARAUJO R B.An Optimal Coverage-preserving Scheme for Wireless Sensor Networks Based on Local Information Exchange[J].Computer Communications,2007,30(14):2708-2720.

[9]XING G L,WANG X R,ZHANG Y F,et al.Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks[J].ACM Transactions on Sensor Networks,2005,1(1):36-72.

[10]LIU Y H,PU J H,ZHANG S,et al.A Localized Coverage Preserving Protocol for Wireless Sensor Networks[J]. Sensors,2009,9(1):281-302.

[11]YU J G,DENG X,YU D X,et al.CWSC:Connected k-coverage Working Sets Construction Algorithm in Wireless Sensor Networks[J].AEU-International Journal of Electronics and Communications,2013,67(11):937-946

[12]LIU Y H,SUO L X,SUN D Y,et al.A Virtual Square Grid-based Coverage Algorithm of Redundant Node for Wireless Sensor Network[J].Journal of Network and Computer Applications,2013,36(2):811-817.

(編輯:齊淑娟)

Coverage algorithm for finding the minimum working sets in WSNs

WANG Aimin1,2,LIU Yongqiang1,ZHANG Jing1,LIU Yanheng1,2
(1.College of Computer Science and Technology,Jilin Univ.,Changchun 130012,China;2.Key Lab. of Symbolic Computation and Knowledge Engineering of Ministry of Edu.,Jilin Univ.,Changchun 130012,China)

Since the existing coverage algorithm has a lot of redundant nodes,a coverage algorithm for finding the minimum working sets in WSNs(FMWS)is proposed.The algorithm is divided into two phases:the first phase runs an existing coverage algorithm;the second phase runs an algorithm that uses fewer working nodes to replace more working nodes,with the number of working nodes continuously decreasing through iteration. Simulation shows that the proposed algorithm can obtain more sleep nodes than other algorithms.It can make the number of working nodes reduce around 10%,so as to prolong the network life.

wireless sensor networks;coverage;sleep scheduling;sleep order

TP393

A

1001-2400(2016)04-0141-06

10.3969/j.issn.1001-2400.2016.04.025

2015-04-13 網絡出版時間：2015-10-21

國家自然科學基金資助項目(61073164)

王愛民(1970-),男,副教授,博士,E-mail:wangam@jlu.edu.cn.

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.050.html