移動(dòng)低占空比傳感網(wǎng)中基于多信標(biāo)消息的低時(shí)延鄰居發(fā)現(xiàn)算法

梁俊斌，周翔，馬方強(qiáng)，蔣嬋，何宗鍵

（1.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004；2.廣西大學(xué)廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣西 南寧 530004；3.奧克蘭大學(xué)網(wǎng)絡(luò)研究中心，奧克蘭 1142）

1 引言

移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)（MWSN,mobile wireless senor network）是由大量具有移動(dòng)特性且資源（能量、通信、存儲(chǔ)、計(jì)算等）有限的傳感器節(jié)點(diǎn)采用無(wú)線多跳通信方式自組織而成的網(wǎng)絡(luò)，已經(jīng)被廣泛應(yīng)用于科學(xué)探索、目標(biāo)跟蹤等領(lǐng)域[1-2]。然而，在真實(shí)場(chǎng)景中，由于節(jié)點(diǎn)存在大量的空閑監(jiān)聽(tīng)時(shí)段，導(dǎo)致能量消耗過(guò)大。目前，低占空比的工作模式逐漸成為節(jié)點(diǎn)節(jié)省能量的重要方式之一。具有低占空比工作模式的移動(dòng)無(wú)線傳感器網(wǎng)絡(luò)，被稱(chēng)為移動(dòng)低占空比傳感網(wǎng)（MLDC-WSN,mobile low-duty-cycle wireless senor network）。近年來(lái)，MLDC-WSN 越來(lái)越受到國(guó)內(nèi)外學(xué)者的關(guān)注。

在MLDC-WSN 中，由于節(jié)點(diǎn)往往通過(guò)隨機(jī)移動(dòng)來(lái)監(jiān)測(cè)目標(biāo)事件，使網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷改變，導(dǎo)致節(jié)點(diǎn)需要花費(fèi)較多的能量和時(shí)間來(lái)發(fā)現(xiàn)其鄰居節(jié)點(diǎn)[3-4]。此外，節(jié)點(diǎn)采用低占空比工作模式，即在一個(gè)工作周期內(nèi)，節(jié)點(diǎn)絕大部分時(shí)間處于睡眠狀態(tài)，僅極小部分時(shí)間處于蘇醒狀態(tài)，這使節(jié)點(diǎn)間需要等待較長(zhǎng)時(shí)間來(lái)發(fā)現(xiàn)彼此[5]。因此，如何低能耗、低時(shí)延地發(fā)現(xiàn)鄰居節(jié)點(diǎn)是一項(xiàng)具有挑戰(zhàn)性的工作，這直接關(guān)系到MLDC-WSN 的壽命和網(wǎng)絡(luò)工作的保障[6-7]。

目前，在已有的低占空比網(wǎng)絡(luò)研究中，鄰居節(jié)點(diǎn)相互發(fā)現(xiàn)的方式主要是通過(guò)設(shè)計(jì)一定的調(diào)度算法來(lái)使一對(duì)節(jié)點(diǎn)同時(shí)喚醒并進(jìn)行消息傳遞，如基于birthday 鄰居發(fā)現(xiàn)協(xié)議[8]、異步發(fā)現(xiàn)協(xié)議[9]、disco[10]、U-connect[11]算法等，這些算法雖然確保了一對(duì)節(jié)點(diǎn)能夠在限定時(shí)延內(nèi)完成彼此發(fā)現(xiàn)，卻需要2 個(gè)節(jié)點(diǎn)等待較長(zhǎng)的時(shí)間以同時(shí)被動(dòng)式蘇醒，然后進(jìn)行相互發(fā)現(xiàn)。但是，如果節(jié)點(diǎn)間可以共享自身睡眠調(diào)度表，則可以通過(guò)主動(dòng)蘇醒的方式來(lái)實(shí)現(xiàn)低時(shí)延、低能耗的相互發(fā)現(xiàn)。

基于上述原理，本文提出了一種基于多信標(biāo)的低時(shí)延鄰居發(fā)現(xiàn)算法，該算法中節(jié)點(diǎn)通過(guò)信息交互獲取彼此下次蘇醒的時(shí)刻，采用主動(dòng)蘇醒的方式來(lái)進(jìn)行相互發(fā)現(xiàn)，分為如下2 個(gè)過(guò)程：節(jié)點(diǎn)可以在睡眠時(shí)間段內(nèi)發(fā)送信標(biāo)（beacon）消息，與鄰居節(jié)點(diǎn)共享下次的蘇醒時(shí)刻；蘇醒的鄰居節(jié)點(diǎn)接收beacon消息，調(diào)整下次發(fā)送beacon 消息的時(shí)間，實(shí)現(xiàn)低時(shí)延的雙向鄰居發(fā)現(xiàn)。例如節(jié)點(diǎn)a 在蘇醒時(shí)間段內(nèi)收到另一節(jié)點(diǎn)b 在睡眠時(shí)間段內(nèi)發(fā)送的信標(biāo)消息，獲知節(jié)點(diǎn)b 是其鄰居節(jié)點(diǎn)；然后，節(jié)點(diǎn)a 在節(jié)點(diǎn)b 蘇醒的時(shí)間段內(nèi)發(fā)送信標(biāo)消息，使節(jié)點(diǎn)b 發(fā)現(xiàn)節(jié)點(diǎn)a，從而實(shí)現(xiàn)雙向的鄰居發(fā)現(xiàn)。

本文的主要貢獻(xiàn)包括2 個(gè)部分：1)基于信標(biāo)消息的鄰居發(fā)現(xiàn)方式，提出了一種基于多信標(biāo)消息的低時(shí)延鄰居發(fā)現(xiàn)算法ready-go；2)通過(guò)理論分析和仿真實(shí)驗(yàn)，將已有算法與提出算法從網(wǎng)絡(luò)能耗、發(fā)現(xiàn)概率、發(fā)現(xiàn)時(shí)延等性能方面進(jìn)行了對(duì)比和分析。

2 相關(guān)工作

目前，可以根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)蘇醒的方式，將已經(jīng)存在的鄰居發(fā)現(xiàn)算法分為被動(dòng)式鄰居發(fā)現(xiàn)和主動(dòng)式鄰居發(fā)現(xiàn)2 種方式。其中，被動(dòng)式鄰居發(fā)現(xiàn)算法是指每個(gè)節(jié)點(diǎn)按照預(yù)先設(shè)定好的睡眠調(diào)度表有規(guī)律地蘇醒，從而進(jìn)行相互發(fā)現(xiàn)，如ENDP（efficient neighbor discovery protocol）、Disco、U-connect、C-tours quorum 等算法；主動(dòng)式鄰居發(fā)現(xiàn)算法是指蘇醒節(jié)點(diǎn)通過(guò)獲知鄰居節(jié)點(diǎn)下次蘇醒時(shí)間，主動(dòng)調(diào)整自身蘇醒時(shí)間，從而進(jìn)行相互發(fā)現(xiàn)，如Searchlight、Nihao、Griassdi、SPND（energy saving selectively proactive neighbor discovery）、GBND（group-based neighbor discovery）等算法。

2.1 被動(dòng)式鄰居發(fā)現(xiàn)算法

早期，Dutta 等[10]提出了Disco 發(fā)現(xiàn)算法，將中國(guó)剩余定理（CRT,Chinese remainder theorem）應(yīng)用到占空比傳感網(wǎng)中來(lái)實(shí)現(xiàn)鄰居節(jié)點(diǎn)的快速發(fā)現(xiàn)。具體步驟如下：每個(gè)節(jié)點(diǎn)選取2 個(gè)素?cái)?shù)，將其中一個(gè)作為自身的工作周期，如果節(jié)點(diǎn)自身的計(jì)時(shí)器能夠整除其工作周期，則節(jié)點(diǎn)蘇醒。該算法保證了任意2 個(gè)節(jié)點(diǎn)能夠在一定的時(shí)限內(nèi)相互發(fā)現(xiàn)，但未考慮節(jié)點(diǎn)因時(shí)鐘偏移而導(dǎo)致發(fā)現(xiàn)時(shí)延過(guò)大的問(wèn)題。

針對(duì)Disco 算法存在的問(wèn)題，Kohvakka 等[12]提出了一種同步低占空比傳感網(wǎng)中高效鄰居發(fā)現(xiàn)協(xié)議（ENDP）。該協(xié)議的基本思想是：1)節(jié)點(diǎn)相互發(fā)現(xiàn)，構(gòu)建鄰居集合；2)節(jié)點(diǎn)工作一段時(shí)間后，蘇醒節(jié)點(diǎn)在兩跳通信范圍內(nèi)發(fā)送信標(biāo)消息，其中，信標(biāo)消息包括節(jié)點(diǎn)有效負(fù)載和同步信息；3)節(jié)點(diǎn)先進(jìn)行時(shí)鐘同步，再根據(jù)節(jié)點(diǎn)負(fù)載信息選擇剩余能量大的蘇醒節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸。該算法雖然保證了節(jié)點(diǎn)在限定時(shí)延內(nèi)的發(fā)現(xiàn)概率，平衡了節(jié)點(diǎn)的能量負(fù)載，但是依然存在平均發(fā)現(xiàn)時(shí)延較高的問(wèn)題。

在Disco 算法的基礎(chǔ)上，Kandhalu 等[11]提出了U-connect 鄰居發(fā)現(xiàn)算法。與Disco 算法相似，該算法首先選擇一個(gè)素?cái)?shù)作為節(jié)點(diǎn)工作周期，并將連續(xù)N個(gè)時(shí)隙構(gòu)建成一個(gè)q×q的網(wǎng)格矩陣。接著，節(jié)點(diǎn)從矩陣中選取第i(1 ≤i≤q)列和第j(1 ≤j≤q)行的一半時(shí)隙作為自身蘇醒時(shí)間段，從而提高了節(jié)點(diǎn)間同時(shí)蘇醒的概率，降低了節(jié)點(diǎn)發(fā)現(xiàn)時(shí)延。但是，該算法明顯增大了節(jié)點(diǎn)的占空比，使空閑監(jiān)聽(tīng)的能耗增大。

針對(duì)U-connect 算法存在的不足，陳良銀等[13]提出了一種新的C-torus quorum 發(fā)現(xiàn)算法，可以應(yīng)用在對(duì)稱(chēng)和非對(duì)稱(chēng)網(wǎng)絡(luò)環(huán)境下進(jìn)行鄰居節(jié)點(diǎn)的發(fā)現(xiàn)。具體過(guò)程如下：首先，節(jié)點(diǎn)選擇一個(gè)h×w網(wǎng)格矩陣的元素總數(shù)n作為工作周期，其中h或w為素?cái)?shù)；其次，從網(wǎng)格矩陣中任意選取某一列c(1 ≤c＜h)，再?gòu)倪@一列中選取某一行r(1≤r≤w)；再次，在該行的c列元素后選取個(gè)元素，如果沒(méi)有個(gè)元素，則返回r行的第一個(gè)元素繼續(xù)選擇；最后，節(jié)點(diǎn)將w-1 個(gè)元素作為蘇醒時(shí)間段，再進(jìn)行鄰居節(jié)點(diǎn)的發(fā)現(xiàn)。該算法基于CRT理論，保證了在一定時(shí)限內(nèi)任意2 個(gè)節(jié)點(diǎn)必然能夠相互發(fā)現(xiàn)。但在最壞情況下的限定發(fā)現(xiàn)時(shí)延較大。

從上述幾種發(fā)現(xiàn)算法可以看出，網(wǎng)絡(luò)節(jié)點(diǎn)均采用被動(dòng)式鄰居發(fā)現(xiàn)的方式，通過(guò)一定的策略來(lái)降低2 個(gè)節(jié)點(diǎn)同時(shí)蘇醒的等待時(shí)間。這種方式的優(yōu)點(diǎn)是任意2 個(gè)節(jié)點(diǎn)間不需要信息交互，但也存在任意2個(gè)節(jié)點(diǎn)間可能需要等待很長(zhǎng)的時(shí)間才能完成相互發(fā)現(xiàn)的缺點(diǎn)。

2.2 主動(dòng)式鄰居發(fā)現(xiàn)算法

Bakht 等[14]提出了Searchlight 算法，主要利用beacon 消息來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)間的快速雙向發(fā)現(xiàn)，其基本思想是：首先，利用節(jié)點(diǎn)蘇醒時(shí)刻之間的偏移量來(lái)設(shè)計(jì)beacon 消息的發(fā)送時(shí)刻；然后，通過(guò)拓展被動(dòng)蘇醒時(shí)間段的長(zhǎng)度，使節(jié)點(diǎn)在被動(dòng)蘇醒時(shí)間段的前后一部分時(shí)間也主動(dòng)蘇醒；最后，當(dāng)所有節(jié)點(diǎn)都有相同的占空比時(shí)，通過(guò)計(jì)算節(jié)點(diǎn)的蘇醒偏移量來(lái)選擇采用確定性方法或概率性方法，提高算法在平均情況下的性能。但是，為了保證該算法的發(fā)現(xiàn)概率和時(shí)延基本呈線性增長(zhǎng)的關(guān)系，各個(gè)節(jié)點(diǎn)間需要相同的占空比。

在Searchlight 算法的基礎(chǔ)上，針對(duì)節(jié)點(diǎn)時(shí)間段槽位不對(duì)齊等問(wèn)題，Qiu 等[15]提出了一種新的鄰居發(fā)現(xiàn)協(xié)議Nihao，可以通過(guò)發(fā)送更多的信標(biāo)消息來(lái)減少空閑監(jiān)聽(tīng)。該協(xié)議基于“多說(shuō)少聽(tīng)（TMLL,talk more listen less）”的原則，節(jié)點(diǎn)將一個(gè)占空比生命周期劃分為n個(gè)時(shí)間段，且每隔m個(gè)時(shí)間段節(jié)點(diǎn)發(fā)送一個(gè)beacon 消息，從而實(shí)現(xiàn)與鄰居節(jié)點(diǎn)的快速發(fā)現(xiàn)。由于在每個(gè)生命周期內(nèi)發(fā)送多個(gè)beacon 消息，該協(xié)議會(huì)導(dǎo)致較高的通信能耗，且未考慮節(jié)點(diǎn)時(shí)鐘偏移等問(wèn)題。

針對(duì)Nihao 協(xié)議存在的不足，Kindt 等[16]針對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)鐘不同步的情況，提出了一種新的Griasdi 協(xié)議，節(jié)點(diǎn)之間通過(guò)相互合作的方式來(lái)降低平均雙向發(fā)現(xiàn)時(shí)延。該協(xié)議的具體過(guò)程是節(jié)點(diǎn)在蘇醒時(shí)間段內(nèi)發(fā)送或接收包含有自身下次蘇醒時(shí)刻的beacon 消息，獲得該beacon 消息的鄰居節(jié)點(diǎn)將適當(dāng)?shù)卣{(diào)整發(fā)送beacon 消息的計(jì)劃，以便在其對(duì)應(yīng)的鄰居節(jié)點(diǎn)下次蘇醒時(shí)刻發(fā)送beacon 消息。該協(xié)議使節(jié)點(diǎn)充分利用發(fā)送beacon 消息來(lái)減少與鄰居節(jié)點(diǎn)雙向發(fā)現(xiàn)的平均時(shí)延，但是它在限定時(shí)延內(nèi)的發(fā)現(xiàn)概率不高。

在Griasdi 協(xié)議的基礎(chǔ)上，梁俊斌等[17]提出了一種低能耗的主動(dòng)式鄰居發(fā)現(xiàn)（SPND）算法，通過(guò)對(duì)移動(dòng)節(jié)點(diǎn)通信范圍內(nèi)的鄰居節(jié)點(diǎn)進(jìn)行劃分，來(lái)減少節(jié)點(diǎn)主動(dòng)蘇醒的次數(shù)，從而降低網(wǎng)絡(luò)能耗。該算法的具體步驟是：首先，根據(jù)節(jié)點(diǎn)移動(dòng)速度預(yù)測(cè)下一時(shí)刻自身鄰居集合；然后，節(jié)點(diǎn)將自身通信范圍劃分為[ 0,R-ΔS]和[R-ΔS,R]這2 個(gè)區(qū)域，這樣對(duì)應(yīng)的鄰居節(jié)點(diǎn)集合被劃分為1G和G2這2 個(gè)集合；最后，節(jié)點(diǎn)在下一次蘇醒時(shí)刻，只需要與集合G2中的節(jié)點(diǎn)相互發(fā)現(xiàn)即可。該算法雖然降低了網(wǎng)絡(luò)通信能耗，但卻依然無(wú)法保證較低的鄰居發(fā)現(xiàn)時(shí)延。

此外，Chen 等[18]提出了一種基于群組的發(fā)現(xiàn)（GBND）方法，節(jié)點(diǎn)之間通過(guò)建立一個(gè)時(shí)間表參考機(jī)制來(lái)加快相互發(fā)現(xiàn)的速度。該方法的基本思想是：節(jié)點(diǎn)B 首先使用傳統(tǒng)雙向發(fā)現(xiàn)方式獲知節(jié)點(diǎn)A的喚醒時(shí)刻；然后，節(jié)點(diǎn)B 主動(dòng)將已知節(jié)點(diǎn)C 的喚醒調(diào)度表發(fā)送給節(jié)點(diǎn)A，使節(jié)點(diǎn)A 可以間接地發(fā)現(xiàn)節(jié)點(diǎn)C，從而將相互發(fā)現(xiàn)的節(jié)點(diǎn)構(gòu)成一個(gè)集合；最后，節(jié)點(diǎn)B 有選擇性地將集合中的部分節(jié)點(diǎn)的睡眠調(diào)度表分享給新加入的節(jié)點(diǎn)。但是，該算法在最壞情況下的節(jié)點(diǎn)發(fā)現(xiàn)時(shí)延較大，且成功率不高。

綜上所述，現(xiàn)存的主動(dòng)式鄰居發(fā)現(xiàn)算法雖然能夠在平均時(shí)延和能耗方面取得較好的平衡，但是依然存在在最壞情況下發(fā)現(xiàn)時(shí)延較大、限定時(shí)延下發(fā)現(xiàn)概率不高等問(wèn)題。

3 系統(tǒng)模型和問(wèn)題描述

首先對(duì)將要使用到的術(shù)語(yǔ)進(jìn)行定義，然后給出帶有信標(biāo)消息的MLDC-WSN 模型及問(wèn)題描述。

3.1 相關(guān)定義

定義1beacon 消息。節(jié)點(diǎn)周期性地廣播給鄰居節(jié)點(diǎn)的信標(biāo)信息。該信息包含的數(shù)據(jù)量較小，常用于傳感器節(jié)點(diǎn)間的相互發(fā)現(xiàn)。

定義2單向鄰居發(fā)現(xiàn)[19]。一個(gè)節(jié)點(diǎn)接收到另一個(gè)節(jié)點(diǎn)發(fā)送的beacon 消息，從而獲知該節(jié)點(diǎn)為自己的鄰居節(jié)點(diǎn)。

定義3雙向鄰居發(fā)現(xiàn)。2 個(gè)節(jié)點(diǎn)彼此收到了對(duì)方發(fā)送的beacon 消息，從而實(shí)現(xiàn)雙向的鄰居發(fā)現(xiàn)。

3.2 系統(tǒng)模型

假設(shè)一個(gè)邊長(zhǎng)為L(zhǎng)×L的矩形區(qū)域部署著n個(gè)移動(dòng)傳感器節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)均采用低占空比工作模式，通信半徑均為R。將MLDC-WSN 視為一個(gè)無(wú)向圖，即Gnet={V,E}，其中，V為節(jié)點(diǎn)的集合，E為節(jié)點(diǎn)間通信邊的集合。此外，MLD C-WSN 具備以下特點(diǎn)。

1)所有節(jié)點(diǎn)的能量有限且不可再生。

2)所有節(jié)點(diǎn)采用隨機(jī)路點(diǎn)（RWP,random way point）模型進(jìn)行移動(dòng)[20]。

3)所有節(jié)點(diǎn)大部分時(shí)間處于睡眠（sleep）狀態(tài)，關(guān)閉除去定時(shí)器以外所有其他功能模塊，只在少部分時(shí)間內(nèi)保持活動(dòng)（active）狀態(tài)來(lái)進(jìn)行事件感知和數(shù)據(jù)傳輸。

3.3 問(wèn)題描述

在傳統(tǒng)的MLDC-WSN 中，節(jié)點(diǎn)處于active 狀態(tài)下才能完成事件感知和數(shù)據(jù)傳輸，如圖1 所示，其中T表示工作周期。在第2、9、16 個(gè)時(shí)間段內(nèi)，節(jié)點(diǎn)i處于active 狀態(tài)，可以主動(dòng)發(fā)送或接收數(shù)據(jù)，而在其余時(shí)間段內(nèi)將無(wú)法發(fā)送或接收數(shù)據(jù)。

圖1 傳統(tǒng)的網(wǎng)絡(luò)模型示意

因此，如果節(jié)點(diǎn)i與節(jié)點(diǎn)j在某個(gè)時(shí)刻t處能夠相互發(fā)現(xiàn)，則需要滿足2 個(gè)條件。

1)在某一時(shí)間段Δt內(nèi)，節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離dij始終不超過(guò)通信半徑，即dij≤R。

2)在時(shí)間段Δt內(nèi)，節(jié)點(diǎn)i與節(jié)點(diǎn)j需要獲知彼此下次蘇醒時(shí)刻，從而進(jìn)行相互發(fā)現(xiàn)。

由上述2 個(gè)條件可知，任意2 個(gè)節(jié)點(diǎn)從可以相互通信的時(shí)刻t0開(kāi)始到完成相互發(fā)現(xiàn)的時(shí)刻t+Δt為止，它們相互發(fā)現(xiàn)的時(shí)延δ為

在一個(gè)工作周期T中，節(jié)點(diǎn)的占空比DC 為節(jié)點(diǎn)蘇醒的時(shí)間段加上節(jié)點(diǎn)發(fā)送信標(biāo)消息所占的時(shí)間之和與T的比值，即。從而可以獲得節(jié)點(diǎn)在一個(gè)工作周期內(nèi)的能耗為Ecost=DC×T×H，其中H為單位時(shí)間內(nèi)節(jié)點(diǎn)的平均能耗。

因此，可以將MLDC-WSN 中低時(shí)延的鄰居發(fā)現(xiàn)問(wèn)題歸納為以最小能耗Ecost實(shí)現(xiàn)發(fā)現(xiàn)時(shí)延L最小化的問(wèn)題，即

如果給定節(jié)點(diǎn)的生命周期T，則可以將問(wèn)題轉(zhuǎn)化為以最小低占空DC 實(shí)現(xiàn)發(fā)現(xiàn)時(shí)延L最小化的問(wèn)題，結(jié)合式(2)，可以表示為

傳統(tǒng)MLDC-WSN 很難獲得較小的節(jié)點(diǎn)鄰居發(fā)現(xiàn)時(shí)延，如何使網(wǎng)絡(luò)中的全部節(jié)點(diǎn)以低能耗實(shí)現(xiàn)快速的鄰居發(fā)現(xiàn)是本文研究的課題。

針對(duì)上述問(wèn)題，本文首先改進(jìn)了MLDC-WSN模型的設(shè)計(jì)，然后提出了一種新的基于多信標(biāo)消息的低時(shí)延鄰居發(fā)現(xiàn)算法ready-go。

4 算法設(shè)計(jì)

4.1 算法的基本思想

在Nihao 算法中，節(jié)點(diǎn)通過(guò)增加beacon 消息的發(fā)送次數(shù)來(lái)減少自身蘇醒的次數(shù)，從而實(shí)現(xiàn)能耗的降低；Griassdi 算法通過(guò)一種互助的方式，使節(jié)點(diǎn)在實(shí)現(xiàn)了單向鄰居發(fā)現(xiàn)后，能盡快地實(shí)現(xiàn)雙向鄰居發(fā)現(xiàn)。在這2 種算法思想的基礎(chǔ)上，本文提出了一種基于多信標(biāo)消息的低時(shí)延鄰居發(fā)現(xiàn)算法即通過(guò)持續(xù)廣播快速響應(yīng)的方式來(lái)實(shí)現(xiàn)低時(shí)延和低能耗的鄰居發(fā)現(xiàn)。“持續(xù)廣播”是指節(jié)點(diǎn)在開(kāi)始進(jìn)行鄰居發(fā)現(xiàn)時(shí)，在一段連續(xù)時(shí)間內(nèi)的每個(gè)時(shí)間段的開(kāi)始片段廣播一個(gè)beacon 消息，該消息中將包含發(fā)送節(jié)點(diǎn)在這段連續(xù)時(shí)間之后的第一次蘇醒時(shí)刻。而“快速響應(yīng)”則指發(fā)送節(jié)點(diǎn)i周?chē)墓?jié)點(diǎn)j在接收到beacon 消息后，主動(dòng)調(diào)整自身下一次beacon 消息的發(fā)送時(shí)間，從而正好使節(jié)點(diǎn)i在蘇醒時(shí)刻能夠接收到節(jié)點(diǎn)j發(fā)送的beacon 消息，實(shí)現(xiàn)低時(shí)延的雙向鄰居發(fā)現(xiàn)。

4.2 算法的詳細(xì)設(shè)計(jì)

ready-go 算法基于TMLL 原則進(jìn)行設(shè)計(jì)，即節(jié)點(diǎn)可以在任意時(shí)間段（包括睡眠時(shí)間段和蘇醒時(shí)間段）中發(fā)送一個(gè)beacon 消息，而對(duì)應(yīng)的鄰居節(jié)點(diǎn)只能在蘇醒時(shí)刻才能接收該beacon 消息。在低占空比網(wǎng)絡(luò)中，由于每個(gè)節(jié)點(diǎn)都擁有自己的占空比，使節(jié)點(diǎn)間具有不同的睡眠調(diào)度方式，且所有節(jié)點(diǎn)的占空比均在同一范圍內(nèi)。假設(shè)節(jié)點(diǎn)可以預(yù)先獲取所有節(jié)點(diǎn)中最小占空比的值，則可以將ready-go 算法分為2 個(gè)過(guò)程：ready 過(guò)程和go 過(guò)程。ready 過(guò)程如圖2所示，go 過(guò)程如圖3 所示。

圖2 ready 過(guò)程

圖3 go 過(guò)程

在ready 過(guò)程中，如果MLDC-WSN 中任意一個(gè)節(jié)點(diǎn)i在某一時(shí)刻t0處蘇醒并進(jìn)行鄰居發(fā)現(xiàn)工作，那么節(jié)點(diǎn)i首先需要根據(jù)已經(jīng)獲取的節(jié)點(diǎn)占空比最小值Γ計(jì)算出需要連續(xù)發(fā)送beacon 消息的次數(shù)。接著，發(fā)送節(jié)點(diǎn)i在之后的N個(gè)時(shí)間段內(nèi)的開(kāi)始時(shí)刻發(fā)送一個(gè)beacon 消息，尋找自己的鄰居節(jié)點(diǎn)。如圖2 所示，假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)占空比的最小值為，則節(jié)點(diǎn)i將從t0開(kāi)始的15 個(gè)時(shí)間段內(nèi)，在每個(gè)時(shí)間段的開(kāi)始時(shí)刻發(fā)送一個(gè)beacon 消息，用于尋找自己的鄰居節(jié)點(diǎn)。同時(shí)，由于Γ是節(jié)點(diǎn)中最小的占空比值，在網(wǎng)絡(luò)通信可靠的情況下，在N個(gè)時(shí)間段內(nèi)，能夠保證節(jié)點(diǎn)i周?chē)ㄐ欧秶鷥?nèi)的節(jié)點(diǎn)（如j、k、l等）都能收到它發(fā)送的beacon 消息。beacon 消息包含發(fā)送節(jié)點(diǎn)i在N個(gè)時(shí)間段后的第一次蘇醒時(shí)刻t1的信息。

在go 過(guò)程中，節(jié)點(diǎn)j、k、l在收到鄰居節(jié)點(diǎn)i的beacon 消息后，會(huì)動(dòng)態(tài)調(diào)整自身下一次發(fā)送beacon 消息的時(shí)間表，以保證在節(jié)點(diǎn)i蘇醒的時(shí)間段內(nèi)發(fā)送beacon 消息，從而進(jìn)行雙向的鄰居發(fā)現(xiàn)。

為了使示意圖更加清晰，節(jié)點(diǎn)占空比設(shè)置的值均稍大于實(shí)際情況中的占空比值。從圖3 中可以發(fā)現(xiàn)，收到節(jié)點(diǎn)i發(fā)送的beacon 消息的節(jié)點(diǎn)j、k、l，會(huì)根據(jù)beacon 消息中包含的t1時(shí)刻的信息，調(diào)整自身beacon 消息發(fā)送的時(shí)刻，使發(fā)送的消息正好能被節(jié)點(diǎn)i在t1時(shí)刻接收到。節(jié)點(diǎn)i處理完t1時(shí)刻接收到的beacon 消息后，構(gòu)建在t1時(shí)刻的鄰居集合，完成從t0時(shí)刻到t1時(shí)刻的雙向鄰居發(fā)現(xiàn)過(guò)程。

此外，考慮到在實(shí)際情況中節(jié)點(diǎn)間存在一定的時(shí)鐘偏移的情況，ready-go 算法通過(guò)為每個(gè)節(jié)點(diǎn)增加一次beacon 消息的發(fā)送來(lái)進(jìn)行解決，即節(jié)點(diǎn)i在ready 過(guò)程中發(fā)送N+1 次beacon 消息；同時(shí)，節(jié)點(diǎn)j、k、l在發(fā)送beacon 消息時(shí)間段的開(kāi)始與結(jié)束時(shí)刻，均發(fā)送一個(gè)beacon 消息。

具體解決方案如圖4 所示，在節(jié)點(diǎn)存在時(shí)鐘偏移的情況下，節(jié)點(diǎn)i發(fā)送的beacon 消息仍然能被通信范圍內(nèi)的其他節(jié)點(diǎn)接收到。首先，在ready 過(guò)程中，節(jié)點(diǎn)i增加一次beacon 消息發(fā)送的次數(shù)；然后，在go 過(guò)程中，為了使接收到beacon 消息的節(jié)點(diǎn)j、k、l所發(fā)送的beacon 消息能被節(jié)點(diǎn)i收到，節(jié)點(diǎn)j、k、l需要在t1時(shí)刻時(shí)間段的開(kāi)始時(shí)刻和結(jié)束時(shí)刻均發(fā)送一個(gè)beacon 消息，以保證節(jié)點(diǎn)i在t1時(shí)刻 時(shí) 間 段 內(nèi) 能 夠 收 到 來(lái) 自 節(jié) 點(diǎn)j、k、l發(fā) 送 的beacon 消息，從而使節(jié)點(diǎn)間以較低的時(shí)延完成雙向鄰居發(fā)現(xiàn)。具體的算法描述如算法1 所示。

算法1ready-go 算法

輸入MLDC-WSN 中每一個(gè)節(jié)點(diǎn)i

輸出每個(gè)節(jié)點(diǎn)i的鄰居結(jié)合Gi

圖4 ready-go 算法示意

4.3 性能分析

4.3.1 節(jié)點(diǎn)發(fā)現(xiàn)時(shí)間表

在ready-go、Nihao 和Griassdi 算法中，每個(gè)節(jié)點(diǎn)蘇醒的時(shí)間和發(fā)送beacon 消息的時(shí)間是相互獨(dú)立的。本節(jié)將使用與U-connect 算法中相似的模型來(lái)定義ready-go 算法中的發(fā)現(xiàn)時(shí)間表。

ready-go 算法中節(jié)點(diǎn)i的發(fā)現(xiàn)時(shí)間表被定義為2 個(gè)二進(jìn)制函數(shù)：ψL(i,t)和ψB(i,t)，分別代表時(shí)刻t的蘇醒時(shí)間段和發(fā)送beacon 消息的時(shí)間段，即

因此，節(jié)點(diǎn)之間的鄰居發(fā)現(xiàn)可以通過(guò)ψL(i,t)和ψB(i,t)來(lái)定義。如果節(jié)點(diǎn)i和節(jié)點(diǎn)j在通信范圍內(nèi)，那么節(jié)點(diǎn)i可以單向發(fā)現(xiàn)鄰居節(jié)點(diǎn)j，可定義為ψL(i,t)=1，ψB(i,t)=1；如果節(jié)點(diǎn)i和節(jié)點(diǎn)j在通信范圍內(nèi)，那么節(jié)點(diǎn)i和節(jié)點(diǎn)j可以實(shí)現(xiàn)雙向發(fā)現(xiàn)鄰居，可定義為

即存在時(shí)刻t1、t2，使在t1時(shí)刻，節(jié)點(diǎn)i處于蘇醒時(shí)間段，節(jié)點(diǎn)j處于beacon 消息發(fā)送時(shí)間段；在t2時(shí)刻，節(jié)點(diǎn)i處于beacon 消息發(fā)送時(shí)間段，節(jié)點(diǎn)j處于蘇醒時(shí)間段。

在ready-go 算法中，節(jié)點(diǎn)的發(fā)現(xiàn)時(shí)間表可以定義為

其中，τi表示節(jié)點(diǎn)i的蘇醒時(shí)刻占空比，τmin表示節(jié)點(diǎn)蘇醒時(shí)刻占空比的最小值，T表示節(jié)點(diǎn)i的工作周期，n表示節(jié)點(diǎn)i在一個(gè)工作周期中的第n+ 1次蘇醒，t1表示節(jié)點(diǎn)i在連續(xù)發(fā)生beacon 消息之后的第一次蘇醒時(shí)刻。

在Nihao 算法中，節(jié)點(diǎn)的發(fā)現(xiàn)時(shí)間表可以定義為

其中，L表示Nihao 算法中節(jié)點(diǎn)的最壞發(fā)現(xiàn)時(shí)延，為節(jié)點(diǎn)的工作周期長(zhǎng)度，即L=T=mn；[t]L表示t對(duì)L取模，[t]L＜m表示節(jié)點(diǎn)每個(gè)工作周期的前m個(gè)時(shí)間段，ma表示第a個(gè)m長(zhǎng)度。

4.3.2 占空比時(shí)延乘積模型

通信能耗（Ecost）和發(fā)現(xiàn)概率（P）是低占空比傳感網(wǎng)中鄰居發(fā)現(xiàn)的重要衡量指標(biāo)。將節(jié)點(diǎn)在一個(gè)工作周期內(nèi)的數(shù)據(jù)接收/發(fā)送的數(shù)據(jù)量與傳輸1 bit 數(shù)據(jù)的平均能耗的乘積作為該節(jié)點(diǎn)的通信能耗，即

其中，DC 為節(jié)點(diǎn)一個(gè)工作周期內(nèi)的占空比值，T為節(jié)點(diǎn)的工作周期，H為節(jié)點(diǎn)發(fā)送/接收1bit 數(shù)據(jù)的平均能耗，B為傳輸帶寬。

由文獻(xiàn)[17]可知，節(jié)點(diǎn)i在時(shí)間t內(nèi)被動(dòng)蘇醒發(fā)現(xiàn)鄰居節(jié)點(diǎn)k的概率為

針對(duì)式(8)，對(duì)于任意給定的節(jié)點(diǎn)，T×H×B通常為一個(gè)常數(shù)c，即Ecost=cDC ；針對(duì)式(9)，可以通過(guò)計(jì)算概率密度函數(shù)獲得任意節(jié)點(diǎn)i發(fā)現(xiàn)所有鄰居節(jié)點(diǎn)的期望時(shí)延，即

經(jīng)上述分析可以發(fā)現(xiàn)，占空比和發(fā)現(xiàn)概率分別是影響節(jié)點(diǎn)通信能耗和發(fā)現(xiàn)時(shí)延的關(guān)鍵因素，使占空比和最壞情況發(fā)現(xiàn)時(shí)延已經(jīng)成為衡量鄰居發(fā)現(xiàn)算法優(yōu)劣的重要指標(biāo)。

由于在TMLL 模型下，節(jié)點(diǎn)的通信能耗主要發(fā)生在接收和發(fā)送消息中，因此，在給定工作周期T的情況下，節(jié)點(diǎn)的占空比DC 包括蘇醒時(shí)間段和睡眠時(shí)隙段發(fā)送beacon 消息的時(shí)間，具體表示為

其中，Nc為在一個(gè)工作周期中節(jié)點(diǎn)蘇醒時(shí)發(fā)送beacon 消息的時(shí)間隙個(gè)數(shù)，即是為了避免重復(fù)計(jì)算beacon消息發(fā)送個(gè)數(shù)；α為節(jié)點(diǎn)發(fā)送一個(gè)beacon 消息所需時(shí)間段長(zhǎng)度的比例。

在WSN 中，節(jié)點(diǎn)的發(fā)現(xiàn)時(shí)延和通信能耗往往是一對(duì)對(duì)立的指標(biāo)，更低的時(shí)延意味著更多的能耗。為了方便比較算法性能，文獻(xiàn)[11,15-16]提出了將占空比與時(shí)延的乘積作為評(píng)價(jià)鄰居發(fā)現(xiàn)算法性能的指標(biāo)。如果2 個(gè)指標(biāo)都小，則它們的乘積也小，算法性能更好。文中采用同樣的評(píng)價(jià)模型將ready-go 算法與其他典型的鄰居發(fā)現(xiàn)算法進(jìn)行性能對(duì)比，占空比和時(shí)延乘積Λ為

其中，L表示最壞情況下的節(jié)點(diǎn)鄰居發(fā)現(xiàn)時(shí)延。

下面將給出ready-go 算法與Nihao 算法的DC值與L值，在ready-go 算法中，節(jié)點(diǎn)的最壞發(fā)現(xiàn)時(shí)延L可以表示為

節(jié)點(diǎn)的占空比DC 可以表示為

在 Nihao 算法中，節(jié)點(diǎn)的最壞發(fā)現(xiàn)時(shí)延L=T=mn，節(jié)點(diǎn)蘇醒時(shí)刻的占空比，則占空比DC 為

因此，Nihao 算法的占空比時(shí)延乘積為

對(duì)于ready-go 算法而言，為了便于比較，在不影響正確性的情況下，可以取且T=mn，則DCready-go可以化簡(jiǎn)為

則ready-go 算法的占空比時(shí)延乘積為

經(jīng)過(guò)上述分析，可以發(fā)現(xiàn)，當(dāng)n＞ 2時(shí)，有DCready-go＜ DCNihao且Lready-go＜LNihao，即ready-go 算法在占空比和最壞情況下的發(fā)現(xiàn)時(shí)延都小于Nihao 算法，使Λready-go明顯優(yōu)于ΛNihao。實(shí)際上，當(dāng)τ i＞τmin時(shí)，ready-go 算法可以得到更優(yōu)的最壞情況下節(jié)點(diǎn)發(fā)現(xiàn)時(shí)延值，以實(shí)現(xiàn)更低的占空比和時(shí)延乘積。

4.3.3 占空比時(shí)延乘積對(duì)比

將本文所提的ready-go 算法與前文提到的典型鄰居發(fā)現(xiàn)算法的占空比時(shí)延乘積進(jìn)行對(duì)比。根據(jù)算法類(lèi)型的不同，在計(jì)算中節(jié)點(diǎn)占空比和最壞情況下發(fā)現(xiàn)時(shí)延時(shí)，各算法盡可能使用相同的參數(shù)，具體對(duì)比情況如表1 所示。

表1 典型算法的占空比時(shí)延乘積對(duì)比

表1 中，n為C-tours quorum 算法中節(jié)點(diǎn)的工作周期的長(zhǎng)度；p1、p2為Disco 算法中選取的2 個(gè)素?cái)?shù)，節(jié)點(diǎn)隨機(jī)選取2 個(gè)素?cái)?shù)之一作為自己的工作周期；T=q2為U-connect 算法中節(jié)點(diǎn)的工作周期；為Searchlight 算法中節(jié)點(diǎn)的工作周期，即將節(jié)點(diǎn)的工作周期分解成一個(gè)寬是高兩倍的矩陣；Nihao 算法中，節(jié)點(diǎn)工作周期為T(mén)=mn，m、n根據(jù)具體的網(wǎng)絡(luò)場(chǎng)景調(diào)整，m表示節(jié)點(diǎn)連續(xù)蘇醒的時(shí)間段個(gè)數(shù)，n表示節(jié)點(diǎn)beacon 消息發(fā)送的次數(shù)；ready-go 算法中，m等價(jià)于節(jié)點(diǎn)的工作周期T乘以節(jié)點(diǎn)的蘇醒時(shí)刻占空比τi，

4.3.4 多信標(biāo)平均能耗

在TMLL 模型中，節(jié)點(diǎn)發(fā)送beacon 的時(shí)刻與節(jié)點(diǎn)的蘇醒時(shí)刻是相互獨(dú)立的。假設(shè)每個(gè)節(jié)點(diǎn)在一個(gè)工作周期內(nèi)的蘇醒時(shí)間段都相同，由式(10)可知，節(jié)點(diǎn)在睡眠時(shí)間段發(fā)送 beacon 消息的能耗為節(jié)點(diǎn)在蘇醒時(shí)發(fā)送信標(biāo)的能耗為αwNc，則節(jié)點(diǎn)在一個(gè)工作周期中發(fā)送beacon 消息的能耗為

其中，B為節(jié)點(diǎn)的傳輸數(shù)據(jù)帶寬，|T|為一個(gè)工作周期中的時(shí)間段個(gè)數(shù)。

由于節(jié)點(diǎn)發(fā)送beacon 消息的時(shí)隙只占一個(gè)時(shí)間段中的極少一部分。結(jié)合式(10)和式(18)可得，Cnon_beacon?Cbeacon，其中Cnon_beacon為節(jié)點(diǎn)在一個(gè)工作周期內(nèi)其余工作的能耗（即Cnon_beacon=aB(ψL(i,t)-Nc)）。因此，在實(shí)際應(yīng)用中，可以通過(guò)對(duì)多個(gè)工作周期內(nèi)節(jié)點(diǎn)睡眠時(shí)刻發(fā)送beacon 消息的能耗和蘇醒工作時(shí)的能耗進(jìn)行累加，求取平均能耗來(lái)替代節(jié)點(diǎn)的多信標(biāo)平均能耗。

5 實(shí)驗(yàn)及對(duì)比分析

本節(jié)通過(guò)實(shí)驗(yàn)仿真來(lái)測(cè)試ready-go 算法的性能，并將該算法的實(shí)驗(yàn)數(shù)據(jù)與前文提到的幾種典型算法的數(shù)據(jù)進(jìn)行對(duì)比。為了降低實(shí)驗(yàn)誤差造成的影響，每組實(shí)驗(yàn)進(jìn)行1 000 次，數(shù)據(jù)取平均值。

5.1 實(shí)驗(yàn)環(huán)境

仿真實(shí)驗(yàn)基于C++語(yǔ)言開(kāi)發(fā)的一個(gè)仿真平臺(tái)，在該平臺(tái)上實(shí)現(xiàn)了ready-go 算法及其他的典型算法。在實(shí)驗(yàn)中，假設(shè)WLDC-WSN 部署在500 m×500 m 的矩形區(qū)域內(nèi)，由完全隨機(jī)分布的500 個(gè)移動(dòng)低占空比節(jié)點(diǎn)組成，如圖5 所示。其中，黑色實(shí)心原點(diǎn)為傳感器節(jié)點(diǎn)，R為節(jié)點(diǎn)通信半徑。假設(shè)節(jié)點(diǎn)的蘇醒占空比值為1%，每個(gè)時(shí)間段長(zhǎng)度為10 ms，其中，節(jié)點(diǎn)的蘇醒占空比不包括節(jié)點(diǎn)在睡眠時(shí)間發(fā)送beacon 消息的時(shí)隙。WLDC-WSN 中節(jié)點(diǎn)默認(rèn)通信半徑為100 m，節(jié)點(diǎn)間信息失效時(shí)間設(shè)置為5 000 個(gè)時(shí)間段，節(jié)點(diǎn)發(fā)送一個(gè)beacon 消息的時(shí)長(zhǎng)為0.54 ms。根據(jù)路徑損耗模型[21]，在距離d上計(jì)算發(fā)送1 bit 數(shù)據(jù)的能量損耗為Et=εdλ+Eele，接收1 bit 數(shù)據(jù)的能量損耗為E r=Eele。其中，ε=10-11，λ=2，Eele=50 ×10-9J 。此外，為方便進(jìn)行算法性能的對(duì)比，ready-go 算法與其他幾種算法的實(shí)驗(yàn)參數(shù)保持一致。

圖5 WLDC-WSN 分布示意

5.2 性能表現(xiàn)

本節(jié)分別從限定時(shí)延的發(fā)現(xiàn)概率、節(jié)點(diǎn)最壞情況下的發(fā)現(xiàn)時(shí)延、網(wǎng)絡(luò)平均能耗等方面進(jìn)行了測(cè)試，并將ready-go 算法與其他典型鄰居發(fā)現(xiàn)算法進(jìn)行了對(duì)比。

5.2.1 限定時(shí)延的發(fā)現(xiàn)概率

在這組實(shí)驗(yàn)中，根據(jù)4.3.2 節(jié)的發(fā)現(xiàn)概率模型，設(shè)定節(jié)點(diǎn)蘇醒占空比為1.4%。在給定限定時(shí)延發(fā)現(xiàn)概率的情況下，測(cè)試了ready-go 算法的數(shù)據(jù)，并與SPND、Nihao、Griassdi 這3 種算法的限定時(shí)延發(fā)現(xiàn)概率進(jìn)行了對(duì)比，結(jié)果如圖6 所示。

圖6 限定時(shí)延的發(fā)現(xiàn)概率

從圖6 中可以發(fā)現(xiàn)，根據(jù)算法限定時(shí)延的發(fā)現(xiàn)概率收斂到100%的速度，將上述4 種算法大致分為3 個(gè)梯隊(duì)：ready-go 算法和Griassdi 算法屬于第一梯隊(duì)，這2 種算法都采用了主動(dòng)調(diào)整beacon 消息發(fā)送時(shí)刻的策略，使節(jié)點(diǎn)能夠在很低的發(fā)現(xiàn)時(shí)延下獲得高的發(fā)現(xiàn)概率；第二梯隊(duì)為采用了多beacon消息發(fā)送的Nihao 算法，也能夠使節(jié)點(diǎn)在較低的發(fā)現(xiàn)時(shí)延下得到高發(fā)現(xiàn)概率；SPND 算法由于beacon消息僅在蘇醒時(shí)間段內(nèi)發(fā)送，且節(jié)點(diǎn)未采用主動(dòng)蘇醒方式，導(dǎo)致其的概率收斂速度較慢，因此排在第三梯隊(duì)。

經(jīng)過(guò)上述對(duì)比可知，ready-go 算法由于采用了持續(xù)廣播快速響應(yīng)的思想，使節(jié)點(diǎn)能在最短的時(shí)間內(nèi)找到所有的鄰居節(jié)點(diǎn)，這使它的限定時(shí)延發(fā)現(xiàn)概率的收斂速度優(yōu)于其他3 種算法。

5.2.2 節(jié)點(diǎn)最壞發(fā)現(xiàn)時(shí)延

在這組實(shí)驗(yàn)中，通過(guò)取節(jié)點(diǎn)蘇醒占空比值的范圍為0.2%～1.4%，測(cè)試了節(jié)點(diǎn)發(fā)現(xiàn)所有鄰居節(jié)點(diǎn)的發(fā)現(xiàn)時(shí)延，實(shí)驗(yàn)結(jié)果如圖7 所示。

圖7 不同占空比下的發(fā)現(xiàn)時(shí)延

從圖7 中可以發(fā)現(xiàn)，隨著節(jié)點(diǎn)蘇醒占空比值的增大，SPND 算法的最壞發(fā)現(xiàn)時(shí)延明顯大于其他3種算法的最壞發(fā)現(xiàn)時(shí)延，ready-go 算法和Griassdi算法能取得較小的最壞發(fā)現(xiàn)時(shí)延。同時(shí)，ready-go算法與其他算法相比，在所有占空比取值情況下都能取得最低的最壞發(fā)現(xiàn)時(shí)延。因此，經(jīng)過(guò)實(shí)驗(yàn)對(duì)比可知，采用共享蘇醒時(shí)刻策略的ready-go 算法，可以使本該處于睡眠狀態(tài)的節(jié)點(diǎn)動(dòng)態(tài)調(diào)整自身蘇醒的時(shí)刻，從而增大了蘇醒狀態(tài)收到beacon 消息的概率，降低了最壞發(fā)現(xiàn)時(shí)延。

5.2.3 網(wǎng)絡(luò)平均能耗

在網(wǎng)絡(luò)能耗的測(cè)試中，每次選取網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)進(jìn)行測(cè)試以評(píng)估網(wǎng)絡(luò)能耗，并通過(guò)多次測(cè)試取平均值來(lái)減少實(shí)驗(yàn)誤差。首先，設(shè)置節(jié)點(diǎn)的傳輸帶寬為B=256 kbit/s，則節(jié)點(diǎn)發(fā)送一次beacon 消息的數(shù)據(jù)量為Sbeacon=Bα。

如圖8 所示，節(jié)點(diǎn)的占空比范圍為0.5%～5%，4 種鄰居發(fā)現(xiàn)算法的通信能耗均隨著節(jié)點(diǎn)蘇醒占空比的增加而呈下降趨勢(shì)。其中，SPND 算法的通信能耗明顯高于其他3 種鄰居發(fā)現(xiàn)算法。而ready-go算法與Nihao 和Griassdi 算法相比，它的節(jié)點(diǎn)平均能耗的下降速率最大，且當(dāng)節(jié)點(diǎn)的占空比大于3.5%時(shí)，ready-go 算法的平均能耗低于其他3 種發(fā)現(xiàn)算法的平均能耗。這表明，隨著節(jié)點(diǎn)占空比的增加，ready-go 算法發(fā)送beacon 消息的次數(shù)會(huì)大幅度減少，使ready-go 算法節(jié)點(diǎn)的平均能耗優(yōu)于其他幾種算法。當(dāng)在較低占空比時(shí)，ready-go 算法的平均能耗雖然較高，但是節(jié)點(diǎn)發(fā)送信標(biāo)的能耗只占一個(gè)蘇醒時(shí)間段能耗的極小一部分，因此并不會(huì)對(duì)節(jié)點(diǎn)正常工作時(shí)的能耗造成過(guò)大的影響。

圖8 節(jié)點(diǎn)平均能耗

6 結(jié)束語(yǔ)

本文提出了一種基于多信標(biāo)消息的低時(shí)延鄰居發(fā)現(xiàn)算法ready-go。該算法通過(guò)獲取網(wǎng)絡(luò)中節(jié)點(diǎn)蘇醒占空比最小值，計(jì)算出持續(xù)發(fā)送beacon 消息的次數(shù)；節(jié)點(diǎn)在開(kāi)始進(jìn)行鄰居發(fā)現(xiàn)工作時(shí)，持續(xù)發(fā)送多個(gè)beacon 消息，保證周?chē)臐撛卩従庸?jié)點(diǎn)都能收到，并通過(guò)調(diào)整自身beacon 消息的發(fā)送時(shí)刻，從而快速實(shí)現(xiàn)雙向的鄰居發(fā)現(xiàn)。理論分析和仿真實(shí)驗(yàn)表明，ready-go 算法與其他典型算法相比，能獲得更小的鄰居發(fā)現(xiàn)時(shí)延。同時(shí)，節(jié)點(diǎn)能夠?qū)崿F(xiàn)限定時(shí)延的發(fā)現(xiàn)概率比現(xiàn)有典型算法的收斂速度更快。