與位置無關的節(jié)點調(diào)度算法比較分析

劉立峰，周軼恒，林志貴，哈　謙，王　璽

（1.天津工業(yè)大學電子與信息工程學院，天津　300387；2.國家海洋技術中心近海海洋環(huán)境觀測與監(jiān)測技術研究室，天津　300112）

?

與位置無關的節(jié)點調(diào)度算法比較分析

劉立峰1，周軼恒1，林志貴1，哈謙2，王璽1

（1.天津工業(yè)大學電子與信息工程學院，天津300387；2.國家海洋技術中心近海海洋環(huán)境觀測與監(jiān)測技術研究室，天津300112）

摘要：無線傳感器網(wǎng)絡中，通過對節(jié)點的合理調(diào)度，可以實現(xiàn)節(jié)點能耗均衡、延長網(wǎng)絡生命周期的目的.分析與位置無關的節(jié)點調(diào)度算法發(fā)現(xiàn)，隨機獨立休眠算法（RIS）不需要調(diào)度時間同步，未考慮節(jié)點死亡對工作概率值p的影響，適應性差；基于部署特征的輕量級節(jié)點調(diào)度算法（LDAS），考慮覆蓋率的影響，但需要頻繁交換鄰居節(jié)點信息；基于測距的睡眠調(diào)度算法（RBSS），通過測距尋找正六邊形覆蓋模型，具有較高的覆蓋度，需要時間同步，未考慮能量均衡.從初始節(jié)點數(shù)、工作節(jié)點數(shù)和網(wǎng)絡覆蓋率3方面仿真驗證說明其性能，為選擇節(jié)點調(diào)度算法以及后續(xù)改進提供指導.

關鍵詞：節(jié)點調(diào)度；位置無關；算法；無線傳感器網(wǎng)絡

如何有效降低節(jié)點能耗是無線傳感器網(wǎng)絡設計過程中所需考慮的主要問題之一[1].一些研究者從面向處理器的動態(tài)電壓調(diào)節(jié)和面向單個節(jié)點的動態(tài)功率管理方面研究降低能耗[2]，這2種策略針對單個節(jié)點的能耗進行優(yōu)化，沒有從整個無線傳感器網(wǎng)絡全局的層面進行優(yōu)化.節(jié)點調(diào)度是通過對全局網(wǎng)絡的節(jié)點工作/睡眠等模式合理調(diào)度，降低網(wǎng)絡能耗.其基本原理是在不影響網(wǎng)絡整體性能的前提下，通過一定的方式對網(wǎng)絡中的時間或空間進行劃分，調(diào)度一部分冗余傳感器節(jié)點進入低功耗模式，剩余節(jié)點執(zhí)行監(jiān)測任務[3].無線傳感器網(wǎng)絡中，為了保障區(qū)域全覆蓋以及網(wǎng)絡的穩(wěn)健性，通常采用大面積、高冗余的部署方式，帶來了網(wǎng)絡中大量冗余節(jié)點.合理調(diào)度冗余節(jié)點，可有效地降低無線通信信道沖突、網(wǎng)絡的吞吐量及網(wǎng)絡能耗[4-7].

節(jié)點調(diào)度算法可分為與位置相關的節(jié)點調(diào)度算法和與位置無關的節(jié)點調(diào)度算法兩大類.基于地理位置的節(jié)點調(diào)度算法通過獲取節(jié)點精確的地理位置信息計算節(jié)點的覆蓋區(qū)域和冗余度，實現(xiàn)節(jié)點調(diào)度，如啟發(fā)式的基于最大化互斥集合個數(shù)的算法（MCMCC）[8]、最優(yōu)地理密度控制算法（OGDC）[9]等.此類算法通常采用全球定位系統(tǒng)GPS或其他定位機制獲取節(jié)點的精確位置信息，節(jié)點成本高，定位消耗能量.與位置無關的節(jié)點調(diào)度算法中，節(jié)點的位置信息無需作為已知條件，節(jié)點通過與鄰居節(jié)點交換信息，獲取鄰居節(jié)點個數(shù)、距離等信息判斷節(jié)點是否為冗余節(jié)點，如隨機獨立休眠算法（RIS）[10]、基于部署特征的輕量級節(jié)點調(diào)度算法（LDAS）[11]、基于測距的睡眠調(diào)度算法（RBSS）[12]等.這類無需定位裝置，降低了節(jié)點成本及能耗，越來越受到研究者的青睞.本文分析與位置無關的節(jié)點調(diào)度算法，通過Matlab仿真平臺，分析其各自節(jié)點調(diào)度的特點，驗證其理論的有效性以及分析其不足之處.

1　與位置無關的節(jié)點調(diào)度算法

針對k度覆蓋無線傳感器網(wǎng)絡，Kumar等[10]提出一種隨機獨立休眠算法（RIS）. RIS算法將網(wǎng)絡時長劃分為多個時間片段，所有節(jié)點的時間片長度相等，每個節(jié)點開始調(diào)度的時間不需要同步.每個時間片段起始時執(zhí)行調(diào)度算法，所有節(jié)點各自以獨立的概率p進入工作狀態(tài)或概率（1-p）進入休眠狀態(tài)，網(wǎng)絡生命周期與概率p成反比.因此，已知網(wǎng)絡生命周期和每個節(jié)點的時間片長度，即可計算出概率p，該算法可以將網(wǎng)絡的生命周期延長p倍. RIS算法需部署最少初始節(jié)點數(shù)量n計算如公式（1）所示.已知監(jiān)測區(qū)域面積、節(jié)點感知半徑r和網(wǎng)絡生命周期的條件下，計算出滿足漸近k度覆蓋所需要部署的最少初始節(jié)點數(shù)量n和節(jié)點進入工作狀態(tài)的概率值p.

式中：φ（np）函數(shù)定義如公式（2）所示.

Gui等[11]基于RIS，并采用基于預設時間表，即每個時間片分為活躍期和休眠期兩部分，其隨機性體現(xiàn)在對每個節(jié)點開始執(zhí)行調(diào)度算法的時間選擇上，增強了網(wǎng)絡動態(tài)性能，降低通信開銷，均衡網(wǎng)絡節(jié)點能耗，但未考慮節(jié)點死亡對工作概率值p的影響，適應性差.

基于節(jié)點均勻隨機部署假設，Wu等[12]提出一種基于部署特征的輕量級節(jié)點調(diào)度算法（LDAS）. LDAS算法在網(wǎng)絡監(jiān)測開始時，根據(jù)覆蓋率P，計算節(jié)點所需的鄰居節(jié)點數(shù)目r，r的計算公式如式（3）所示.

各節(jié)點交換信息，獲取自身的實際鄰居節(jié)點數(shù)n，如果鄰居節(jié)點數(shù)n超過r，節(jié)點隨機選擇（n-r）個鄰居節(jié)點，發(fā)送節(jié)點關閉信息.如果節(jié)點收到的關閉信息次數(shù)超過閾值b（公式（4）），則該節(jié)點在一段隨機延時后進入睡眠狀態(tài).如果在隨機延時過程中，節(jié)點的部分鄰居節(jié)點進入睡眠狀態(tài)，導致節(jié)點的鄰居節(jié)點數(shù)目小于r，則該節(jié)點不進入睡眠狀態(tài). LDAS算法無需節(jié)點位置信息和時間同步機制，在一定程度上能同時保證覆蓋率和連通性，但只能采取均勻部署，需要頻繁交換鄰居節(jié)點信息.

借鑒OGDC算法思想，Yen等[13]提出一種與地理位置無關的基于測距的睡眠調(diào)度算法（RBSS）.假設監(jiān)測區(qū)域中的節(jié)點均勻隨機部署，節(jié)點通信半徑為感知半徑的倍時，RBSS算法可以在不需要精確地理位置信息的情況下，通過測距在已部署節(jié)點中尋找和逼近正六邊形覆蓋模型[14-15]，保證網(wǎng)絡的覆蓋率和連通性. RBSS算法將網(wǎng)絡生命周期劃分為固定時間長度段（輪）.每輪起始時，節(jié)點隨機競爭成為招募節(jié)點.招募節(jié)點發(fā)布招募消息，其鄰居節(jié)點接收到招募消息后，首先判斷2個節(jié)點間的距離，如果節(jié)點距離小于傳輸半徑的1/2，則節(jié)點進入睡眠狀態(tài)，否則節(jié)點發(fā)送響應消息.招募節(jié)點接收到響應消息后，選擇距其最遠的鄰居節(jié)點作為協(xié)作節(jié)點，循環(huán)招募新的協(xié)作節(jié)點，直至協(xié)作節(jié)點數(shù)等于6或無法招募到協(xié)作節(jié)點.招募完成后，招募節(jié)點和協(xié)作節(jié)點執(zhí)行監(jiān)測任務，其余節(jié)點進入睡眠狀態(tài)，直至本輪結束. RBSS具有較高的覆蓋度，保證網(wǎng)絡節(jié)點的通信連接，但需要時間同步，未考慮能量均衡.

2　算法仿真分析

2.1仿真環(huán)境

采用Matlab仿真平臺分別對上述節(jié)點調(diào)度算法進行仿真.仿真環(huán)境設定為網(wǎng)絡區(qū)域規(guī)模為100m×100 m，節(jié)點感知半徑為10 m，節(jié)點通信半徑為10～17 m.

2.2仿真結果與分析

2.2.1 RIS算法仿真分析

RIS算法根據(jù)網(wǎng)絡生命周期、節(jié)點感知半徑、網(wǎng)絡區(qū)域面積預測節(jié)點睡眠概率p和網(wǎng)絡達到k度覆蓋所需初始節(jié)點數(shù)量n.假定每個節(jié)點在其生命周期中可執(zhí)行5次調(diào)度，即睡眠概率（1-p）等于0.8.滿足k度覆蓋的初始節(jié)點數(shù)量n變化如圖1所示；k度覆蓋的工作節(jié)點數(shù)量如圖2所示.

從圖1和圖2看出，RIS算法所需初始節(jié)點數(shù)量較大，即使當k=1時，也需要部署1 805個節(jié)點，每輪工作節(jié)點數(shù)為368個.

圖1　k度覆蓋初始節(jié)點數(shù)量曲線Fig.1 Number curve of nodes on k-coverage

圖2　k度覆蓋工作節(jié)點數(shù)量曲線Fig.2 Number curve of working nodes on k-coverage

2.2.2 LDAS算法仿真分析

LDAS算法根據(jù)覆蓋率P計算出每個節(jié)點所需最少鄰居節(jié)點數(shù)r，據(jù)此執(zhí)行節(jié)點調(diào)度算法.假設初始節(jié)點數(shù)分別為1 000、1 500、2 000時，需求覆蓋率與實際覆蓋率的關系如圖3所示.需求覆蓋率與工作節(jié)點數(shù)量的關系如圖4所示.由圖3看出，LDAS算法的實際覆蓋率與需求覆蓋率的誤差在-2%至3%之間，LDAS算法是有效的.由圖4看出，不同需求覆蓋率下，初始部署節(jié)點數(shù)量不同，執(zhí)行LDAS調(diào)度算法后，工作節(jié)點數(shù)不隨初始節(jié)點數(shù)量的增加而增加.需求覆蓋率為85%時，工作節(jié)點數(shù)保持在125至135之間，平均為130個工作節(jié)點.需求覆蓋率為90%時，工作節(jié)點數(shù)保持在165～ 168，平均為167個工作節(jié)點.需求覆蓋率為95%時，工作節(jié)點數(shù)保持在230～233，平均為232個工作節(jié)點. 2.2.3 RBSS算法仿真分析

RBSS算法基于正六邊形覆蓋模型，節(jié)點通過測距獲知鄰居節(jié)點的距離選取最優(yōu)工作節(jié)點，其工作節(jié)點數(shù)目隨節(jié)點總數(shù)變化曲線如圖5所示，網(wǎng)絡覆蓋率隨節(jié)點總數(shù)變化曲線如圖6所示.

從圖5和圖6看出，RBSS調(diào)度算法中，當網(wǎng)絡節(jié)點數(shù)大于200時，網(wǎng)絡覆蓋率即超過96%，僅需62個工作節(jié)點.網(wǎng)絡部署節(jié)點數(shù)達到1 000時，網(wǎng)絡覆蓋率為99.88%，工作節(jié)點數(shù)為79個.

圖3　需求覆蓋率與實際覆蓋率關系曲線Fig.3 Curves of actual coverage with requirements coverage

圖4　需求覆蓋率與工作節(jié)點數(shù)量關系曲線Fig.4 Curves of working nodes number with different requirements coverage

圖5　工作節(jié)點數(shù)目隨節(jié)點總數(shù)變化曲線Fig.5 Curve of number of working nodes with total number of nodes

圖6　網(wǎng)絡覆蓋率隨節(jié)點總數(shù)變化曲線Fig.6 Curve of Network coverage with total number of nodes

2.2.4 3種算法仿真比較

選取在網(wǎng)絡覆蓋率接近100%時的初始節(jié)點數(shù)目和工作節(jié)點數(shù)目，比較RIS、LDAS、RBSS 3種算法的性能，其結果如表1所示.

表1　3種算法仿真結果比較Tab.1 Comparison of simulation results of three algorithms

由表1可知，RBSS算法與RIS算法網(wǎng)絡覆蓋率相差僅0.02%時，RBSS算法比RIS算法初始節(jié)點數(shù)目減少805個（44.6%）、工作節(jié)點數(shù)目減少289個（78.5%），RBSS算法優(yōu)于RIS算法.由表1還可得知，RBSS算法與LDAS算法初始節(jié)點數(shù)目均為1 000時，RBSS算法比LDAS算法工作節(jié)點數(shù)目減少151個（65.7%）、網(wǎng)絡覆蓋率增加4.88%，RBSS算法優(yōu)于LDAS算法.

3　結語

RIS算法只需設定監(jiān)測區(qū)域面積、節(jié)點感知半徑和網(wǎng)絡生命周期即可計算節(jié)點休眠概率p和網(wǎng)絡初始節(jié)點數(shù)量n，算法實現(xiàn)簡單，各節(jié)點只需以概率p進入工作狀態(tài)，無需與鄰居節(jié)點交換信息，但是網(wǎng)絡滿足k度覆蓋所需的初始節(jié)點數(shù)量較大. LDAS算法根據(jù)需求覆蓋率計算所需鄰居節(jié)點數(shù)目，通過去除多余鄰居節(jié)點減少冗余工作節(jié)點，但是在執(zhí)行調(diào)度過程中，節(jié)點間需要頻繁交換鄰居節(jié)點信息，容易造成能量消耗和網(wǎng)絡擁堵，且需要工作節(jié)點數(shù)目較多.與RIS 和LDAS算法相比，RBSS算法具有良好的調(diào)度效果，在相同條件下，僅需較少的工作節(jié)點即可達到較高的網(wǎng)絡覆蓋率，但需要測量節(jié)點間距離，增加網(wǎng)絡成本. RBSS算法在實現(xiàn)過程中，始終由招募節(jié)點執(zhí)行協(xié)作節(jié)點招募，因此相對其他節(jié)點會消耗較多的能量；當網(wǎng)絡部署節(jié)點密度變大時，6個協(xié)作節(jié)點可能無法與招募節(jié)點形成無漏洞覆蓋，形成覆蓋漏洞.

參考文獻：

[1]陸游，禹素萍.一種能量可計算的星型無線傳感器網(wǎng)絡協(xié)議[J].天津工業(yè)大學學報，2013，32（4）：60-65. LU Y，YU S P. An energy star computable wireless sensor network protocol[J]. Journal of Tianjin Polytechnic University，2013，32（4）：60-65（in Chinese）.

[2] WANG Lei，WEI Ruizhong，TIAN Zihong. Cluster based node scheduling method for wireless sensor networks [J]. Science China Information Sciences，2012，55（4）：755-764.

[3] XUE Weilian，CHI Zhongxian. A flexible node scheduling scheme of minimum delay and energy efficient for wireless sensor networks[J]. International Journal of Parallel，Emergent and Distributed Systems，2012，27（2）：123-131.

[4] KHOSRAVI Hamid. Optimal node scheduling for desired percentage of coverage in wireless sensor networks [J]. Wireless Sensor Network，2012，4（5）：127-132.

[5]胡湘華，楊學軍.傳感網(wǎng)節(jié)點調(diào)度方法綜述[J].計算機工程與科學，2008，30（3）：93-96，129. HU X H，YANG X J. Review of sensor network node scheduling methods[J]. Journal of Computer Engineering and Science，2008，30（3）：93-96，129（in Chinese）.

[6]洪鋒，褚紅偉，金宗科，等.無線傳感器網(wǎng)絡應用系統(tǒng)最新進展綜述[J].計算機研究與發(fā)展，2010，47（S2）：81-87. HONG F，ZHU H W，JIN Z K，et al. Review of latest development in wireless sensor network applications [J]. Journal of Computer Research and Development，2010，47（S2）：81-87 （in Chinese）.

[7] WANG Lei，WEI Ruizhong，LIN Yaping，et al. A clique base node scheduling method for wireless sensor networks [J]. Journal of Network and Computer Applications，2010，33（4）：383-396.

[8] SLIJEPCEVIC Sasa，POTKONJAK Miodrag. Power efficient organization of wireless sensor networks[C]//IEEE International Conference on Communication（ICC）. Helsinki：Finland，IEEE，2001：472-476.

[9] ZHANG Honghai，HOU Jennifer C. Maintaining sensing coverage and connectivity in large sensor networks [J]. Ad Hoc & Sensor Wireless Networks，2004，1（2）：89-124.

[10] KUMAR Santosh，LAI Ten H，BALOGH Jozsef. On k coverage in a mostly sleeping sensor network [J]. Wireless Networks，2003，14（3）：277-294.

[11] GUI Chao，MOHAPATRA Prasant. Power conservation and quality of surveillancein target tracking sensor networks [C]// Proceedings of the 10th Annual International Conference on Mobile Computing and Networking. Philadelphia：ACM，2004：129-143.

[12] WU Kui，GAO Yong，LI Fulu，et al. Lightweight deploymentaware scheduling for wireless sensor networks [J]. Mobile Networks and Applications，2005，10（6）：837-852.

[13] YENLihsing，CHENGYangmin.Range-basedsleep scheduling （RBSS）for wireless sensor networks [J]. Wireless Personal Communications，2009，48（3）：411-423.

[14]趙仕俊，張朝暉.無線傳感器網(wǎng)絡正六邊形節(jié)點覆蓋模型研究[J].計算機工程，2010，36（20）：113-115，118. ZHAO S J，ZHANG Z H. Research on wireless sensor networks' hexagonal node coverage model[J]. Journal of Computer Engineering，2010，36（20）：113-115，118（in Chinese）.

[15]趙仕俊，路嘉鑫，張朝暉.無線傳感器網(wǎng)絡一維區(qū)域隨機覆蓋研究[J].昆明理工大學學報：理工版，2010，35（4）：71-75. ZHAO S J，LU J X，ZHANG Z H. Research on a one-dimensional area randomized covering in wireless sensor networks[J]. Journal of Kunming University of Science And Technology：Natural Science Edition，2010，35（4）：71-75（in Chinese）.

Comparison and analysis of node scheduling algorithms on position-independent in WSNs

LIU Li-feng1，ZHOU Yi-heng1，LIN Zhi-gui1，HA Qian2，WANG Xi1
（1. School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China；2. Laboratory of Marine Environment Observation and Monitoring Technology of Offshore，National Ocean Technology Center，Tianjin 300112，China）

Abstract：In wireless sensor networks，by reasonable scheduling of nodes，energy consumption balance and prolonging the

network life cycle are achieved. The position-independent node scheduling algorithms is analyzed，and it is found that a random independent sleep algorithm（RIS）does not require scheduled time synchronization，and does not consider the influences of a node death on its running probability p and has poor adaptability. A lightweight node scheduling algorithm（LDAS）based on the deployment features considers the impact of coverage，and then it needs to exchange the information of neighbor nodes frequently. A range based sleep scheduling algorithm （RBSS）looks for regular hexagon coverage model by measuring distance with high coverage. The RBSS needs time synchronization and does not consider nodes energy balance. By simulation，the performance of the algorithms is compared from the number of the initial nodes and working nodes, and network coverage，which provides guidance for selection of valid node scheduling algorithms and subsequent improvement.

Key words：node scheduling；position-independent；algorithms；wireless sensor network

通信作者：劉立峰（1975—），男，博士，講師，主要研究方向為智能信息處理. E-mail：liulifeng@tjpu.edu.cn

收稿日期：2015-10-19基金項目：國家自然科學基金資助項目（61372011）

DOI：10.3969/j.issn.1671-024x.2016.01.010

中圖分類號：TN921

文獻標志碼：A

文章編號：1671－024X（2016）01－0050－04