與位置無(wú)關(guān)的節(jié)點(diǎn)調(diào)度算法比較分析

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

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

?

與位置無(wú)關(guān)的節(jié)點(diǎn)調(diào)度算法比較分析

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

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

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

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

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

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

1　與位置無(wú)關(guān)的節(jié)點(diǎn)調(diào)度算法

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

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

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

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

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

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

2　算法仿真分析

2.1仿真環(huán)境

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

2.2仿真結(jié)果與分析

2.2.1 RIS算法仿真分析

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

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

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

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

2.2.2 LDAS算法仿真分析

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

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

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

圖3　需求覆蓋率與實(shí)際覆蓋率關(guān)系曲線Fig.3 Curves of actual coverage with requirements coverage

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

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

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

2.2.4 3種算法仿真比較

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

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

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

3　結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]陸游，禹素萍.一種能量可計(jì)算的星型無(wú)線傳感器網(wǎng)絡(luò)協(xié)議[J].天津工業(yè)大學(xué)學(xué)報(bào)，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]胡湘華，楊學(xué)軍.傳感網(wǎng)節(jié)點(diǎn)調(diào)度方法綜述[J].計(jì)算機(jī)工程與科學(xué)，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ú)線傳感器網(wǎng)絡(luò)應(yīng)用系統(tǒng)最新進(jìn)展綜述[J].計(jì)算機(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ú)線傳感器網(wǎng)絡(luò)正六邊形節(jié)點(diǎn)覆蓋模型研究[J].計(jì)算機(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ú)線傳感器網(wǎng)絡(luò)一維區(qū)域隨機(jī)覆蓋研究[J].昆明理工大學(xué)學(xué)報(bào)：理工版，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—），男，博士，講師，主要研究方向?yàn)橹悄苄畔⑻幚? E-mail：liulifeng@tjpu.edu.cn

收稿日期：2015-10-19基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61372011）

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

中圖分類號(hào)：TN921

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1671－024X（2016）01－0050－04