林志貴，程曉偉，劉英平，王 鵬，王 璽

（1.天津工業(yè)大學(xué)電子與信息工程學(xué)院，天津300387；2.國(guó)家海洋技術(shù)中心近海海洋環(huán)境觀測(cè)與監(jiān)測(cè)技術(shù)研究室，天津300112；3.天津工業(yè)大學(xué)機(jī)械工程學(xué)院，天津300387；4.天津工業(yè)大學(xué)現(xiàn)代機(jī)電裝備技術(shù)天津市重點(diǎn)實(shí)驗(yàn)室，天津300387）

水環(huán)境無(wú)線傳感網(wǎng)中的分布式招募調(diào)度算法

林志貴1，2，程曉偉1，劉英平3，4，王 鵬2，王 璽1

（1.天津工業(yè)大學(xué)電子與信息工程學(xué)院，天津300387；2.國(guó)家海洋技術(shù)中心近海海洋環(huán)境觀測(cè)與監(jiān)測(cè)技術(shù)研究室，天津300112；3.天津工業(yè)大學(xué)機(jī)械工程學(xué)院，天津300387；4.天津工業(yè)大學(xué)現(xiàn)代機(jī)電裝備技術(shù)天津市重點(diǎn)實(shí)驗(yàn)室，天津300387）

針對(duì)基于測(cè)距的睡眠調(diào)度算法（RBSS）招募節(jié)點(diǎn)能耗大，導(dǎo)致網(wǎng)絡(luò)過(guò)快失效問(wèn)題，結(jié)合水環(huán)境無(wú)線傳感網(wǎng)規(guī)則部署，采用分布式思想，提出一種基于測(cè)距的分布式招募調(diào)度算法（RBDRS）.RBDRS算法采用分布式招募方法，將協(xié)作節(jié)點(diǎn)招募的任務(wù)轉(zhuǎn)移到新招募的協(xié)作節(jié)點(diǎn)上，均衡網(wǎng)絡(luò)能耗.招募節(jié)點(diǎn)通過(guò)測(cè)距招募距其最遠(yuǎn)的鄰居節(jié)點(diǎn)作為協(xié)作節(jié)點(diǎn)，協(xié)作節(jié)點(diǎn)再依次為招募節(jié)點(diǎn)招募新的協(xié)作節(jié)點(diǎn)，直至無(wú)法招募到新的協(xié)作節(jié)點(diǎn).仿真實(shí)驗(yàn)結(jié)果表明：與RBSS算法相比，RBDRS算法可均衡網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期.

節(jié)點(diǎn)調(diào)度；RBDRS；分布式招募；水環(huán)境無(wú)線傳感網(wǎng)

近年來(lái)，一些學(xué)者將無(wú)線傳感器技術(shù)應(yīng)用于水環(huán)境監(jiān)測(cè)，形成水環(huán)境無(wú)線傳感網(wǎng)[1-2].利用廉價(jià)的無(wú)線傳感器節(jié)點(diǎn)監(jiān)測(cè)數(shù)據(jù)并組建網(wǎng)絡(luò)，形成對(duì)水環(huán)境的區(qū)域監(jiān)測(cè)，獲得水環(huán)境區(qū)域狀況.這對(duì)于水環(huán)境監(jiān)測(cè)來(lái)說(shuō)，由點(diǎn)監(jiān)測(cè)擴(kuò)展到面監(jiān)測(cè)，具有里程碑意義.

水環(huán)境無(wú)線傳感網(wǎng)中，除了突發(fā)事件（如污染物排放、油輪泄漏等）外，數(shù)據(jù)變化緩慢，節(jié)點(diǎn)通常采用規(guī)則的部署方式.為了保證網(wǎng)絡(luò)的全覆蓋、穩(wěn)定性，部署節(jié)點(diǎn)有一定的冗余.如果這些冗余節(jié)點(diǎn)沒(méi)有好的調(diào)度，節(jié)點(diǎn)可能發(fā)送相同的信息，造成節(jié)點(diǎn)能量的浪費(fèi)以及網(wǎng)絡(luò)擁堵.節(jié)點(diǎn)調(diào)度[3-7]通過(guò)一定方法對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分組，在不影響區(qū)域覆蓋、通信質(zhì)量、任務(wù)等前提下，使一部分節(jié)點(diǎn)處于活躍狀態(tài)而另一部分節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，節(jié)省節(jié)點(diǎn)能量，延長(zhǎng)網(wǎng)絡(luò)的生命周期.

與位置無(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).Kumar等[8]通過(guò)研究k度覆蓋、網(wǎng)絡(luò)區(qū)域面積、節(jié)點(diǎn)感知半徑、網(wǎng)絡(luò)生命周期和初始部署節(jié)點(diǎn)數(shù)量、節(jié)點(diǎn)休眠概率之間的關(guān)系，提出一種隨機(jī)獨(dú)立休眠調(diào)度算法，可實(shí)現(xiàn)k度覆蓋，實(shí)現(xiàn)簡(jiǎn)單，但所需初始節(jié)點(diǎn)數(shù)量較大.Wu等[9]研究鄰居節(jié)點(diǎn)數(shù)目與網(wǎng)絡(luò)覆蓋率之間的關(guān)系，提出一種輕量級(jí)節(jié)點(diǎn)調(diào)度算法.根據(jù)需求覆蓋率計(jì)算所需鄰居節(jié)點(diǎn)數(shù)目，去除多余鄰居節(jié)點(diǎn)，實(shí)現(xiàn)減少冗余工作節(jié)點(diǎn)的目的.該算法在執(zhí)行過(guò)程中，節(jié)點(diǎn)間需要頻繁交換鄰居節(jié)點(diǎn)信息，易造成能量消耗和網(wǎng)絡(luò)擁堵.Yen等[10]提出一種與地理位置無(wú)關(guān)的基于測(cè)距的睡眠調(diào)度算法（RBSS），假設(shè)網(wǎng)絡(luò)區(qū)域中的節(jié)點(diǎn)均勻隨機(jī)部署，節(jié)點(diǎn)通信半徑為感知半徑的倍時(shí)，RBSS算法通過(guò)測(cè)距在已部署節(jié)點(diǎn)中尋找和逼近正六邊形覆蓋模型，保證網(wǎng)絡(luò)的覆蓋率和連通性，但是RBSS算法未考慮節(jié)點(diǎn)調(diào)度過(guò)程中招募節(jié)點(diǎn)能耗過(guò)大，導(dǎo)致招募節(jié)點(diǎn)過(guò)早死亡，影響網(wǎng)絡(luò)生命周期情況.

從搜索文獻(xiàn)看，目前針對(duì)水環(huán)境無(wú)線傳感網(wǎng)的節(jié)點(diǎn)調(diào)度算法尚未見(jiàn)報(bào)道.本文針對(duì)RBSS算法中由招募節(jié)點(diǎn)發(fā)布協(xié)作節(jié)點(diǎn)招募消息，節(jié)點(diǎn)頻繁發(fā)送和接收數(shù)據(jù)，導(dǎo)致能量消耗過(guò)快及網(wǎng)絡(luò)過(guò)快失效，基于分布式思想，結(jié)合水環(huán)境無(wú)線傳感網(wǎng)規(guī)則部署，提出基于測(cè)距的分布式招募調(diào)度算法（RBDRS）.

1 假設(shè)條件及問(wèn)題描述

1.1 相關(guān)假設(shè)

本文對(duì)水環(huán)境無(wú)線傳感網(wǎng)做出如下假設(shè)：網(wǎng)絡(luò)區(qū)域?yàn)橐粋€(gè)二維平面上的正方形區(qū)域；網(wǎng)絡(luò)中節(jié)點(diǎn)同構(gòu)，節(jié)點(diǎn)具有相同的感知半徑Rs和通信半徑Rt；節(jié)點(diǎn)采用布爾感知模型（0-1模型），即感知半徑Rs內(nèi)發(fā)生的事件以概率1感知，Rs外發(fā)生的事件不能感知，概率為0；節(jié)點(diǎn)可實(shí)現(xiàn)時(shí)間同步，利用節(jié)點(diǎn)間的無(wú)線信號(hào)強(qiáng)度計(jì)算鄰近節(jié)點(diǎn)間的距離，節(jié)點(diǎn)不具備獲取位置信息及移動(dòng)能力；網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)采用隨機(jī)分布，存在大量冗余節(jié)點(diǎn)，不存在孤立節(jié)點(diǎn).

1.2 問(wèn)題描述

文獻(xiàn)[11]已證明二維區(qū)域正六邊形覆蓋模型，且節(jié)點(diǎn)通信半徑大于或等于倍感知半徑，可獲得最小全覆蓋且連通.對(duì)于節(jié)點(diǎn)調(diào)度來(lái)說(shuō)，實(shí)現(xiàn)正六邊形覆蓋問(wèn)題轉(zhuǎn)化為當(dāng)Rs時(shí)，如何選擇中心工作節(jié)點(diǎn)S，以及如何圍繞節(jié)點(diǎn)S尋找6個(gè)相距Rt的鄰居工作節(jié)點(diǎn)C1—C6的問(wèn)題.中心工作節(jié)點(diǎn)S稱(chēng)為招募節(jié)點(diǎn)、6個(gè)鄰居工作節(jié)點(diǎn)稱(chēng)為協(xié)作節(jié)點(diǎn)，如圖1所示.

圖1 正六邊形部署示意圖Fig.1 Schematic of network hexagonal deployment

2 RBDRS算法設(shè)計(jì)

2.1 基本思想

RBDRS算法將網(wǎng)絡(luò)生命周期劃分為長(zhǎng)度相同的若干輪，每輪開(kāi)始時(shí)執(zhí)行節(jié)點(diǎn)調(diào)度策略，如圖2所示.

圖2 RBDRS調(diào)度策略示意圖Fig.2 Scheduling policy schematic of RBDRS algorithm

假設(shè)節(jié)點(diǎn)S1競(jìng)爭(zhēng)成為招募節(jié)點(diǎn)，其余節(jié)點(diǎn)等待被招募節(jié)點(diǎn)招募為協(xié)作節(jié)點(diǎn)或滿足睡眠條件進(jìn)入睡眠狀態(tài).S1發(fā)出協(xié)作節(jié)點(diǎn)招募消息，S1的鄰居節(jié)點(diǎn)判斷其與S1的距離，如果距離小于Dm（Dm=Rt/2，2個(gè)工作節(jié)點(diǎn)間的最小距離），節(jié)點(diǎn)在本輪進(jìn)入睡眠狀態(tài)；如果距離大于Dm，則節(jié)點(diǎn)發(fā)送協(xié)作節(jié)點(diǎn)響應(yīng).招募節(jié)點(diǎn)S1收到協(xié)作節(jié)點(diǎn)響應(yīng)消息后，選擇距其最遠(yuǎn)的節(jié)點(diǎn)C11作為協(xié)作節(jié)點(diǎn).C11發(fā)送協(xié)作節(jié)點(diǎn)請(qǐng)求消息，為S1招募新的協(xié)作節(jié)點(diǎn).只有S1的鄰居節(jié)點(diǎn)響應(yīng)C11的請(qǐng)求消息，收到請(qǐng)求消息的節(jié)點(diǎn)睡眠規(guī)則與節(jié)點(diǎn)S1相同.依次類(lèi)推，招募C12—C16為協(xié)作節(jié)點(diǎn).如果C16無(wú)法招募到協(xié)作節(jié)點(diǎn)，則由C11發(fā)送協(xié)作節(jié)點(diǎn)招募消息.如果C11也無(wú)法招募到協(xié)作節(jié)點(diǎn)，則由招募節(jié)點(diǎn)S1發(fā)送協(xié)作節(jié)點(diǎn)招募消息.如果S1也無(wú)法再招募到協(xié)作節(jié)點(diǎn)，則本輪招募結(jié)束，招募節(jié)點(diǎn)和協(xié)作節(jié)點(diǎn)都進(jìn)入工作狀態(tài).

2.2 算法結(jié)構(gòu)

RBDRS算法將網(wǎng)絡(luò)時(shí)間劃分為相同時(shí)長(zhǎng)的輪，如圖3所示.每輪開(kāi)始為招募節(jié)點(diǎn)競(jìng)爭(zhēng)階段，任意節(jié)點(diǎn)都可通過(guò)競(jìng)爭(zhēng)成為招募節(jié)點(diǎn)，招募節(jié)點(diǎn)間不互為鄰居節(jié)點(diǎn)，即每個(gè)招募節(jié)點(diǎn)的傳輸范圍內(nèi)不存在其它招募節(jié)點(diǎn).其后，進(jìn)入招募協(xié)作節(jié)點(diǎn)階段，招募節(jié)點(diǎn)按照招募協(xié)議招募協(xié)作節(jié)點(diǎn).最后，招募節(jié)點(diǎn)和協(xié)作節(jié)點(diǎn)作為工作節(jié)點(diǎn)執(zhí)行任務(wù)，其余節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)，直至本輪結(jié)束.網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)擁有自己獨(dú)立的ID號(hào)以及鄰居節(jié)點(diǎn)表和工作節(jié)點(diǎn)表.鄰居節(jié)點(diǎn)表用來(lái)保存當(dāng)前已知鄰居節(jié)點(diǎn)的ID號(hào)和節(jié)點(diǎn)距離.工作節(jié)點(diǎn)表用來(lái)保存當(dāng)前已知招募節(jié)點(diǎn)和協(xié)作節(jié)點(diǎn)的ID號(hào)和節(jié)點(diǎn)距離.

圖3 節(jié)點(diǎn)調(diào)度時(shí)間結(jié)構(gòu)圖Fig.3 Chart of nodes scheduling time

2.3 算法流程

節(jié)點(diǎn)依據(jù)不同條件，其狀態(tài)可以相互轉(zhuǎn)換，如圖4所示.

圖4 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖Fig.4 Transition diagram of node states

2.3.1 招募節(jié)點(diǎn)競(jìng)爭(zhēng)

每輪開(kāi)始 ，節(jié)點(diǎn)進(jìn)入招募節(jié)點(diǎn)競(jìng)爭(zhēng)階段，經(jīng)過(guò)一段隨機(jī)延時(shí)后，節(jié)點(diǎn)周期性發(fā)送招募節(jié)點(diǎn)請(qǐng)求消息，直至節(jié)點(diǎn)競(jìng)爭(zhēng)成功或失敗.招募節(jié)點(diǎn)競(jìng)爭(zhēng)流程圖如圖5所示.首先對(duì)本輪調(diào)度過(guò)程中所用變量進(jìn)行初始化，包括鄰居節(jié)點(diǎn)表、工作節(jié)點(diǎn)表和招募節(jié)點(diǎn)ID初始化等.等待調(diào)度開(kāi)始信號(hào).接收到開(kāi)始調(diào)度信號(hào)后，啟動(dòng)本輪調(diào)度總計(jì)時(shí)器，隨機(jī)延時(shí)，執(zhí)行招募節(jié)點(diǎn)競(jìng)爭(zhēng)程序.在招募節(jié)點(diǎn)競(jìng)爭(zhēng)過(guò)程中，如果節(jié)點(diǎn)始終未接收到其他節(jié)點(diǎn)的招募節(jié)點(diǎn)競(jìng)爭(zhēng)消息，則節(jié)點(diǎn)成為招募節(jié)點(diǎn)，招募節(jié)點(diǎn)ID設(shè)置為本機(jī)ID，工作狀態(tài)修改為協(xié)作節(jié)點(diǎn)招募狀態(tài)；反之，節(jié)點(diǎn)成為普通節(jié)點(diǎn)，節(jié)點(diǎn)狀態(tài)修改為普通節(jié)點(diǎn).

圖5 招募節(jié)點(diǎn)競(jìng)爭(zhēng)流程圖Fig.5 Flowchart of competing recruitment node

2.3.2 協(xié)作節(jié)點(diǎn)招募

節(jié)點(diǎn)成為招募節(jié)點(diǎn)或協(xié)作節(jié)點(diǎn)后，進(jìn)入?yún)f(xié)作節(jié)點(diǎn)招募狀態(tài).節(jié)點(diǎn)首先發(fā)送協(xié)作節(jié)點(diǎn)招募消息，啟動(dòng)定時(shí)Ts，Ts為2次數(shù)據(jù)接收的最長(zhǎng)間隔時(shí)間.在Ts延時(shí)內(nèi)，節(jié)點(diǎn)循環(huán)查詢接收標(biāo)志位.如果接收到數(shù)據(jù)，則對(duì)接收到的數(shù)據(jù)進(jìn)行處理.如果為協(xié)作節(jié)點(diǎn)響應(yīng)消息，比較接收到數(shù)據(jù)的距離和本地存儲(chǔ)的最大距離，保存兩者中較大的距離，及其相應(yīng)的節(jié)點(diǎn)ID.重新啟動(dòng)定時(shí)Ts，等待接收新的協(xié)作節(jié)點(diǎn)響應(yīng)消息.

如果在Ts延時(shí)內(nèi)，節(jié)點(diǎn)未收到新的協(xié)作節(jié)點(diǎn)響應(yīng)消息，則節(jié)點(diǎn)判斷是否招募到新的協(xié)作節(jié)點(diǎn).如果招募到新的協(xié)作節(jié)點(diǎn)，發(fā)送協(xié)作節(jié)點(diǎn)確認(rèn)消息，如果發(fā)送確認(rèn)消息的節(jié)點(diǎn)是由招募節(jié)點(diǎn)招募到的，節(jié)點(diǎn)狀態(tài)修改為招募完成狀態(tài)，否則節(jié)點(diǎn)狀態(tài)修改為工作狀態(tài).如果沒(méi)有招募到新的協(xié)作節(jié)點(diǎn)，節(jié)點(diǎn)狀態(tài)修改為工作狀態(tài)，開(kāi)始環(huán)境監(jiān)測(cè)工作.協(xié)作節(jié)點(diǎn)招募流程圖如圖6所示.

2.3.3 普通節(jié)點(diǎn)（待招募）

節(jié)點(diǎn)在招募節(jié)點(diǎn)競(jìng)爭(zhēng)過(guò)程中失敗，成為普通節(jié)點(diǎn)，等待被招募為協(xié)作節(jié)點(diǎn)或進(jìn)入休眠狀態(tài).等待被招募的過(guò)程中，節(jié)點(diǎn)循環(huán)查詢接收標(biāo)志位.如果接收到數(shù)據(jù)，計(jì)算發(fā)送數(shù)據(jù)節(jié)點(diǎn)與本節(jié)點(diǎn)之間的距離，對(duì)接收到的數(shù)據(jù)進(jìn)行解析，判斷為何種指令消息.指令消息共分為3種：協(xié)作節(jié)點(diǎn)請(qǐng)求消息、協(xié)作節(jié)點(diǎn)響應(yīng)消息和協(xié)作節(jié)點(diǎn)確認(rèn)消息.普通節(jié)點(diǎn)流程圖如圖7所示.

圖6 協(xié)作節(jié)點(diǎn)招募流程圖Fig.6 Flowchart of cooperating recruitment nodes

圖7 普通節(jié)點(diǎn)流程圖Fig.7 Flowchart of ordinary nodes

（1）如果收到消息為協(xié)作節(jié)點(diǎn)請(qǐng)求消息，判斷節(jié)點(diǎn)距離是否小于Dm（兩個(gè)工作節(jié)點(diǎn)間的最小距離）.如果節(jié)點(diǎn)距離不大于Dm，節(jié)點(diǎn)直接進(jìn)入睡眠狀態(tài)；否則計(jì)算協(xié)作節(jié)點(diǎn)響應(yīng)延時(shí)Tr，打包協(xié)作節(jié)點(diǎn)響應(yīng)消息，啟動(dòng)定時(shí)Tr.Tr延時(shí)結(jié)束后，發(fā)送協(xié)作節(jié)點(diǎn)響應(yīng)消息.

（2）如果收到消息為協(xié)作節(jié)點(diǎn)響應(yīng)消息，節(jié)點(diǎn)判斷本身是否已啟動(dòng)定時(shí)Tr，即是否接收到協(xié)作節(jié)點(diǎn)請(qǐng)求消息.如果沒(méi)有啟動(dòng)定時(shí)Tr，則對(duì)該響應(yīng)消息不做處理.如果該消息為本網(wǎng)絡(luò)協(xié)作節(jié)點(diǎn)響應(yīng)消息，則比較本節(jié)點(diǎn)Tr與接收到響應(yīng)消息中Tr大小.如果本節(jié)點(diǎn)Tr大于接收到響應(yīng)消息中Tr，則表明發(fā)布響應(yīng)消息的節(jié)點(diǎn)比本節(jié)點(diǎn)更適合成為協(xié)作節(jié)點(diǎn)（該節(jié)點(diǎn)距離招募節(jié)點(diǎn)更遠(yuǎn)），本節(jié)點(diǎn)停止定時(shí)Tr，取消協(xié)作節(jié)點(diǎn)響應(yīng)消息發(fā)送，否則繼續(xù)等待Tr延時(shí)后，發(fā)送協(xié)作節(jié)點(diǎn)響應(yīng)消息.

（3）如果收到消息為協(xié)作節(jié)點(diǎn)確認(rèn)消息，則節(jié)點(diǎn)更新工作節(jié)點(diǎn)表，消息中的協(xié)作節(jié)點(diǎn)ID是否為本節(jié)點(diǎn)ID.如果本節(jié)點(diǎn)成為協(xié)作節(jié)點(diǎn)，則更新招募節(jié)點(diǎn)ID為消息中的招募節(jié)點(diǎn)ID，節(jié)點(diǎn)狀態(tài)修改為協(xié)作節(jié)點(diǎn)招募狀態(tài).

2.3.4 招募完成

如果節(jié)點(diǎn)為招募節(jié)點(diǎn)，或招募節(jié)點(diǎn)招募的協(xié)作節(jié)點(diǎn)，則節(jié)點(diǎn)在招募到協(xié)作節(jié)點(diǎn)后進(jìn)入招募完成狀態(tài).招募完成流程圖如圖8所示.節(jié)點(diǎn)進(jìn)入招募完成狀態(tài)，啟動(dòng)定時(shí)Tw.在延時(shí)Tw到達(dá)前，節(jié)點(diǎn)循環(huán)查詢接收標(biāo)志位，如果收到數(shù)據(jù)，則判斷是否為協(xié)作節(jié)點(diǎn)確認(rèn)消息.如果是協(xié)作節(jié)點(diǎn)確認(rèn)消息，更新工作節(jié)點(diǎn)表，判斷是否為本網(wǎng)絡(luò)協(xié)作節(jié)點(diǎn)確認(rèn)消息，如果是，則重啟定時(shí)Tw，否則，不做處理.延時(shí)Tw完成后，判斷是否第一次進(jìn)入招募完成狀態(tài)，如果是，表明節(jié)點(diǎn)還沒(méi)有更改招募方向，則節(jié)點(diǎn)狀態(tài)修改為協(xié)作節(jié)點(diǎn)請(qǐng)求狀態(tài).如果不是，表明節(jié)點(diǎn)在更改招募方向后，再次沒(méi)有招募到新的協(xié)作節(jié)點(diǎn)，則節(jié)點(diǎn)修改為工作狀態(tài).

2.3.5 工作或睡眠狀態(tài)

節(jié)點(diǎn)進(jìn)入工作狀態(tài)，開(kāi)始執(zhí)行水環(huán)境監(jiān)測(cè)任務(wù)，直至本輪結(jié)束，節(jié)點(diǎn)狀態(tài)修改為招募節(jié)點(diǎn)競(jìng)爭(zhēng)狀態(tài)，開(kāi)始下一輪招募.工作狀態(tài)流程圖如圖9所示.節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)，關(guān)閉收發(fā)器，直至本輪結(jié)束，節(jié)點(diǎn)狀態(tài)修改為招募節(jié)點(diǎn)競(jìng)爭(zhēng)狀態(tài)，開(kāi)始下一輪招募.睡眠狀態(tài)流程圖如圖10所示.

圖8 招募完成流程圖Fig.8 Flowchart of recruitment completion

圖9 工作狀態(tài)流程圖Fig.9 Flowchart of working state

圖10 睡眠狀態(tài)流程圖Fig.10 Flowchart of sleep state

3 仿真與分析

實(shí)驗(yàn)仿真基于Matlab仿真平臺(tái).網(wǎng)絡(luò)規(guī)模為50m× 50 m，隨機(jī)部署終端節(jié)點(diǎn)9個(gè)，數(shù)據(jù)傳輸錯(cuò)誤率和丟包率均為0，節(jié)點(diǎn)感知半徑Rs為10 m，通信半徑Rt為17 m.節(jié)點(diǎn)感知模型為圓形，節(jié)點(diǎn)具備測(cè)距能力，節(jié)點(diǎn)初始能量為1 J，所有節(jié)點(diǎn)起始時(shí)均為喚醒狀態(tài).為了便于計(jì)算網(wǎng)絡(luò)覆蓋率，將網(wǎng)絡(luò)劃分為1 m×1 m的方格，如果方格的中心被某個(gè)節(jié)點(diǎn)感知到，則認(rèn)為方格區(qū)域被覆蓋[12].覆蓋率為被覆蓋方格數(shù)與劃分的方格總數(shù)比值.如果網(wǎng)絡(luò)是分割的，則只計(jì)算擁有最多連通節(jié)點(diǎn)（最大覆蓋率）的區(qū)域.

3.1 網(wǎng)絡(luò)覆蓋情況

網(wǎng)絡(luò)覆蓋情況如圖11所示.基于RBSS算法的網(wǎng)絡(luò)覆蓋情況如圖11（a）所示.由圖11（a）可以看出，網(wǎng)絡(luò)工作節(jié)點(diǎn)數(shù)為7個(gè)，其中招募節(jié)點(diǎn)1個(gè)，協(xié)作節(jié)點(diǎn)6個(gè)，睡眠節(jié)點(diǎn)2個(gè)，節(jié)點(diǎn)5競(jìng)爭(zhēng)成為招募節(jié)點(diǎn)，在其鄰居節(jié)點(diǎn)中依次招募距其最遠(yuǎn)的6個(gè)節(jié)點(diǎn)作為協(xié)作節(jié)點(diǎn).

圖11 網(wǎng)絡(luò)覆蓋情況圖Fig.11 Figure of network coverage

基于RBDRS算法的網(wǎng)絡(luò)覆蓋情況如圖11（b）所示.由圖11（b）可以看出，網(wǎng)絡(luò)工作節(jié)點(diǎn)數(shù)為7個(gè)，其中招募節(jié)點(diǎn)3個(gè)，協(xié)作節(jié)點(diǎn)4個(gè)，睡眠節(jié)點(diǎn)2個(gè)，網(wǎng)絡(luò)覆蓋模型近似正六邊形.RBDRS算法招募節(jié)點(diǎn)數(shù)大于RBSS算法，減少節(jié)點(diǎn)頻繁發(fā)送和接收數(shù)據(jù)帶來(lái)能量消耗.比較圖11（a）和圖11（b），與BRSS算法相比，基于RBDRS算法的網(wǎng)絡(luò)覆蓋模型更加趨近于正六邊形覆蓋.

3.2 網(wǎng)絡(luò)生命周期

隨著時(shí)間延長(zhǎng)，網(wǎng)絡(luò)中的部分節(jié)點(diǎn)因能量的耗盡而死亡.需要進(jìn)一步對(duì)網(wǎng)絡(luò)生命周期進(jìn)行分析，假定所有節(jié)點(diǎn)時(shí)間同步，每100 s（輪）存活節(jié)點(diǎn)同時(shí)喚醒，執(zhí)行節(jié)點(diǎn)調(diào)度算法，決定節(jié)點(diǎn)在本輪的工作狀態(tài)（睡眠或工作）.

RBSS算法和RBDRS算法的網(wǎng)絡(luò)覆蓋率隨時(shí)間變化曲線如圖12所示.當(dāng)網(wǎng)絡(luò)覆蓋率小于50%時(shí)，認(rèn)為網(wǎng)絡(luò)失效.比較圖12（a）和圖12（b）可以看出，當(dāng)時(shí)間超過(guò)3 040 s時(shí)，RBSS算法的網(wǎng)絡(luò)覆蓋率小于50%，而RBDRS算法需要時(shí)間超過(guò)6 420 s.與RBSS算法相比，RBDRS算法的網(wǎng)絡(luò)有效時(shí)間延長(zhǎng)了111%.造成這種結(jié)果原因在于，在算法執(zhí)行過(guò)程中，RBSS算法總是由招募節(jié)點(diǎn)來(lái)發(fā)布協(xié)作節(jié)點(diǎn)招募消息，節(jié)點(diǎn)頻繁發(fā)送和接收數(shù)據(jù)，導(dǎo)致能量消耗過(guò)快，一般招募節(jié)點(diǎn)連續(xù)工作兩輪后就會(huì)死亡.RBDRS算法的協(xié)作節(jié)點(diǎn)招募消息由每次新招募的協(xié)作節(jié)點(diǎn)發(fā)布，將數(shù)據(jù)發(fā)送所消耗的能量平均分給每個(gè)協(xié)作節(jié)點(diǎn)，使整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)能量消耗更加均衡，有效地延長(zhǎng)網(wǎng)絡(luò)生命周期.

圖12 網(wǎng)絡(luò)覆蓋率隨時(shí)間變化曲線Fig.12 Curve of network coverage with times

4 結(jié)語(yǔ)

基于測(cè)距的睡眠調(diào)度算法（RBSS）通過(guò)招募節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)調(diào)度，招募節(jié)點(diǎn)能耗過(guò)大，造成其過(guò)早死亡，影響網(wǎng)絡(luò)的生命周期.針對(duì)這個(gè)問(wèn)題，本文基于分布式思想，結(jié)合水環(huán)境無(wú)線傳感網(wǎng)通常采用的規(guī)則部署，提出基于測(cè)距的分布式招募調(diào)度算法（RBDRS）.給出了該算法適用的假設(shè)條件，基于正六邊形節(jié)點(diǎn)覆蓋模型，RBDRS算法考慮到招募節(jié)點(diǎn)在算法執(zhí)行過(guò)程中能量消耗過(guò)高而導(dǎo)致節(jié)點(diǎn)快速死亡的情況，將協(xié)同節(jié)點(diǎn)招募的任務(wù)轉(zhuǎn)移到每個(gè)新招募的協(xié)作節(jié)點(diǎn)上，使網(wǎng)絡(luò)的能量消耗更加均衡.

仿真實(shí)驗(yàn)結(jié)果表明，與RBSS算法相比，RBDRS算法均衡網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期.

[1]郭忠文，羅漢江，洪鋒，等.水下無(wú)線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2010，47（3）：377-389.

[2]ALBALADEJO Cristina,SANCHEZ Pedro,IBORRA Andrés, et al.Wireless sensor networks for oceanographic monitoring：A systematic review[J].Sensor，2010，10（7）：6948-6968.

[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.

[6]洪鋒，褚紅偉，金宗科，等.無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用系統(tǒng)最新進(jìn)展綜述[J].計(jì)算機(jī)研究與發(fā)展，2010，47（S2）：81-87.

[7]陸游，禹素萍，姜華，等.一種能量可計(jì)算的星型無(wú)線傳感器網(wǎng)絡(luò)協(xié)議[J].天津工業(yè)大學(xué)學(xué)報(bào)，2013，32（4）：60-65.

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

[9]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.

[10]YEN Lihsing，CHENG Yangmin.Range-based sleep scheduling（RBSS）for wireless sensor networks[J].Wireless Personal Communications，2009，48（3）：411-423.

[11]趙仕俊，張朝暉.無(wú)線傳感器網(wǎng)絡(luò)正六邊形節(jié)點(diǎn)覆蓋模型研究[J].計(jì)算機(jī)工程，2010，36（20）：113-115，118.

[12]王璽.無(wú)線傳感監(jiān)測(cè)網(wǎng)節(jié)點(diǎn)調(diào)度算法研究及應(yīng)用[D].天津：天津工業(yè)大學(xué)，2015.

Distributed recruit scheduling algorithm in water environment wireless sensor network

LIN Zhi-gui1，2，CHENG Xiao-wei1，LIU Ying-ping3，4，WANG Peng2，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；3.School of Mechanical Engineering，Tianjin Polytechnic University，Tianjin 300387，China；4.Tianjin City Key Laboratory of Modern Mechatronics Equipment Technology，Tianjin Polytechnic University，Tianjin 300387，China）

Aiming at the problem of the range-based sleep scheduling algorithm（RBSS），which the energy consumption of recruit node is too large and affects the network life cycle，on the basis of the regular coverage model in water environment wireless sensor network，combined with the distributed thinking，a Range Based Distributed Recruit Scheduling（RBDRS）is proposed.The RBDRS algorithm adopts method of distributed recruitment，which transferrs recruited task of cooperating nodes to new-recruitment cooperative nodes in order to balance network energy consumption.Recruitment nodes recruit its farthest neighbor nodes as collaborative nodes by their distance，collaborative nodes recruit new collaborative nodes for recruitment nodes in turn until they are unable to recruit new collaborative nodes.Simulation results show that compared with the RBSS algorithm，the RBDRS algorithm can effectively balance network energy consumption and prolong the network lifetime.

node scheduling；range based distributed recruit scheduling（RBDRS）；distributed recruitment；water environment wireless sensor networks

TN929.3

A

1671－024X（2015）06－0061－06

10.3969/j.issn.1671-024x.2015.06.013

2015-07-16

國(guó)家自然科學(xué)基金資助項(xiàng)目（61372011）

林志貴（1974—），男，副教授，碩士生導(dǎo)師，主要研究方向?yàn)闊o(wú)線傳感網(wǎng)絡(luò)及智能信息處理.E-mail：linzhigui@tjpu.edu.cn