移動低占空比傳感網中基于多信標消息的低時延鄰居發現算法

梁俊斌，周翔，馬方強，蔣嬋，何宗鍵

（1.廣西大學計算機與電子信息學院，廣西 南寧 530004；2.廣西大學廣西多媒體通信與網絡技術重點實驗室，廣西 南寧 530004；3.奧克蘭大學網絡研究中心，奧克蘭 1142）

1 引言

移動無線傳感器網絡（MWSN,mobile wireless senor network）是由大量具有移動特性且資源（能量、通信、存儲、計算等）有限的傳感器節點采用無線多跳通信方式自組織而成的網絡，已經被廣泛應用于科學探索、目標跟蹤等領域[1-2]。然而，在真實場景中，由于節點存在大量的空閑監聽時段，導致能量消耗過大。目前，低占空比的工作模式逐漸成為節點節省能量的重要方式之一。具有低占空比工作模式的移動無線傳感器網絡，被稱為移動低占空比傳感網（MLDC-WSN,mobile low-duty-cycle wireless senor network）。近年來，MLDC-WSN 越來越受到國內外學者的關注。

在MLDC-WSN 中，由于節點往往通過隨機移動來監測目標事件，使網絡拓撲結構不斷改變，導致節點需要花費較多的能量和時間來發現其鄰居節點[3-4]。此外，節點采用低占空比工作模式，即在一個工作周期內，節點絕大部分時間處于睡眠狀態，僅極小部分時間處于蘇醒狀態，這使節點間需要等待較長時間來發現彼此[5]。因此，如何低能耗、低時延地發現鄰居節點是一項具有挑戰性的工作，這直接關系到MLDC-WSN 的壽命和網絡工作的保障[6-7]。

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

基于上述原理，本文提出了一種基于多信標的低時延鄰居發現算法，該算法中節點通過信息交互獲取彼此下次蘇醒的時刻，采用主動蘇醒的方式來進行相互發現，分為如下2 個過程：節點可以在睡眠時間段內發送信標（beacon）消息，與鄰居節點共享下次的蘇醒時刻；蘇醒的鄰居節點接收beacon消息，調整下次發送beacon 消息的時間，實現低時延的雙向鄰居發現。例如節點a 在蘇醒時間段內收到另一節點b 在睡眠時間段內發送的信標消息，獲知節點b 是其鄰居節點；然后，節點a 在節點b 蘇醒的時間段內發送信標消息，使節點b 發現節點a，從而實現雙向的鄰居發現。

本文的主要貢獻包括2 個部分：1)基于信標消息的鄰居發現方式，提出了一種基于多信標消息的低時延鄰居發現算法ready-go；2)通過理論分析和仿真實驗，將已有算法與提出算法從網絡能耗、發現概率、發現時延等性能方面進行了對比和分析。

2 相關工作

目前，可以根據網絡節點蘇醒的方式，將已經存在的鄰居發現算法分為被動式鄰居發現和主動式鄰居發現2 種方式。其中，被動式鄰居發現算法是指每個節點按照預先設定好的睡眠調度表有規律地蘇醒，從而進行相互發現，如ENDP（efficient neighbor discovery protocol）、Disco、U-connect、C-tours quorum 等算法；主動式鄰居發現算法是指蘇醒節點通過獲知鄰居節點下次蘇醒時間，主動調整自身蘇醒時間，從而進行相互發現，如Searchlight、Nihao、Griassdi、SPND（energy saving selectively proactive neighbor discovery）、GBND（group-based neighbor discovery）等算法。

2.1 被動式鄰居發現算法

早期，Dutta 等[10]提出了Disco 發現算法，將中國剩余定理（CRT,Chinese remainder theorem）應用到占空比傳感網中來實現鄰居節點的快速發現。具體步驟如下：每個節點選取2 個素數，將其中一個作為自身的工作周期，如果節點自身的計時器能夠整除其工作周期，則節點蘇醒。該算法保證了任意2 個節點能夠在一定的時限內相互發現，但未考慮節點因時鐘偏移而導致發現時延過大的問題。

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

在Disco 算法的基礎上，Kandhalu 等[11]提出了U-connect 鄰居發現算法。與Disco 算法相似，該算法首先選擇一個素數作為節點工作周期，并將連續N個時隙構建成一個q×q的網格矩陣。接著，節點從矩陣中選取第i(1 ≤i≤q)列和第j(1 ≤j≤q)行的一半時隙作為自身蘇醒時間段，從而提高了節點間同時蘇醒的概率，降低了節點發現時延。但是，該算法明顯增大了節點的占空比，使空閑監聽的能耗增大。

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

從上述幾種發現算法可以看出，網絡節點均采用被動式鄰居發現的方式，通過一定的策略來降低2 個節點同時蘇醒的等待時間。這種方式的優點是任意2 個節點間不需要信息交互，但也存在任意2個節點間可能需要等待很長的時間才能完成相互發現的缺點。

2.2 主動式鄰居發現算法

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

在Searchlight 算法的基礎上，針對節點時間段槽位不對齊等問題，Qiu 等[15]提出了一種新的鄰居發現協議Nihao，可以通過發送更多的信標消息來減少空閑監聽。該協議基于“多說少聽（TMLL,talk more listen less）”的原則，節點將一個占空比生命周期劃分為n個時間段，且每隔m個時間段節點發送一個beacon 消息，從而實現與鄰居節點的快速發現。由于在每個生命周期內發送多個beacon 消息，該協議會導致較高的通信能耗，且未考慮節點時鐘偏移等問題。

針對Nihao 協議存在的不足，Kindt 等[16]針對網絡節點時鐘不同步的情況，提出了一種新的Griasdi 協議，節點之間通過相互合作的方式來降低平均雙向發現時延。該協議的具體過程是節點在蘇醒時間段內發送或接收包含有自身下次蘇醒時刻的beacon 消息，獲得該beacon 消息的鄰居節點將適當地調整發送beacon 消息的計劃，以便在其對應的鄰居節點下次蘇醒時刻發送beacon 消息。該協議使節點充分利用發送beacon 消息來減少與鄰居節點雙向發現的平均時延，但是它在限定時延內的發現概率不高。

在Griasdi 協議的基礎上，梁俊斌等[17]提出了一種低能耗的主動式鄰居發現（SPND）算法，通過對移動節點通信范圍內的鄰居節點進行劃分，來減少節點主動蘇醒的次數，從而降低網絡能耗。該算法的具體步驟是：首先，根據節點移動速度預測下一時刻自身鄰居集合；然后，節點將自身通信范圍劃分為[ 0,R-ΔS]和[R-ΔS,R]這2 個區域，這樣對應的鄰居節點集合被劃分為1G和G2這2 個集合；最后，節點在下一次蘇醒時刻，只需要與集合G2中的節點相互發現即可。該算法雖然降低了網絡通信能耗，但卻依然無法保證較低的鄰居發現時延。

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

綜上所述，現存的主動式鄰居發現算法雖然能夠在平均時延和能耗方面取得較好的平衡，但是依然存在在最壞情況下發現時延較大、限定時延下發現概率不高等問題。

3 系統模型和問題描述

首先對將要使用到的術語進行定義，然后給出帶有信標消息的MLDC-WSN 模型及問題描述。

3.1 相關定義

定義1beacon 消息。節點周期性地廣播給鄰居節點的信標信息。該信息包含的數據量較小，常用于傳感器節點間的相互發現。

定義2單向鄰居發現[19]。一個節點接收到另一個節點發送的beacon 消息，從而獲知該節點為自己的鄰居節點。

定義3雙向鄰居發現。2 個節點彼此收到了對方發送的beacon 消息，從而實現雙向的鄰居發現。

3.2 系統模型

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

1)所有節點的能量有限且不可再生。

2)所有節點采用隨機路點（RWP,random way point）模型進行移動[20]。

3)所有節點大部分時間處于睡眠（sleep）狀態，關閉除去定時器以外所有其他功能模塊，只在少部分時間內保持活動（active）狀態來進行事件感知和數據傳輸。

3.3 問題描述

在傳統的MLDC-WSN 中，節點處于active 狀態下才能完成事件感知和數據傳輸，如圖1 所示，其中T表示工作周期。在第2、9、16 個時間段內，節點i處于active 狀態，可以主動發送或接收數據，而在其余時間段內將無法發送或接收數據。

圖1 傳統的網絡模型示意

因此，如果節點i與節點j在某個時刻t處能夠相互發現，則需要滿足2 個條件。

1)在某一時間段Δt內，節點i與節點j之間的距離dij始終不超過通信半徑，即dij≤R。

2)在時間段Δt內，節點i與節點j需要獲知彼此下次蘇醒時刻，從而進行相互發現。

由上述2 個條件可知，任意2 個節點從可以相互通信的時刻t0開始到完成相互發現的時刻t+Δt為止，它們相互發現的時延δ為

在一個工作周期T中，節點的占空比DC 為節點蘇醒的時間段加上節點發送信標消息所占的時間之和與T的比值，即。從而可以獲得節點在一個工作周期內的能耗為Ecost=DC×T×H，其中H為單位時間內節點的平均能耗。

因此，可以將MLDC-WSN 中低時延的鄰居發現問題歸納為以最小能耗Ecost實現發現時延L最小化的問題，即

如果給定節點的生命周期T，則可以將問題轉化為以最小低占空DC 實現發現時延L最小化的問題，結合式(2)，可以表示為

傳統MLDC-WSN 很難獲得較小的節點鄰居發現時延，如何使網絡中的全部節點以低能耗實現快速的鄰居發現是本文研究的課題。

針對上述問題，本文首先改進了MLDC-WSN模型的設計，然后提出了一種新的基于多信標消息的低時延鄰居發現算法ready-go。

4 算法設計

4.1 算法的基本思想

在Nihao 算法中，節點通過增加beacon 消息的發送次數來減少自身蘇醒的次數，從而實現能耗的降低；Griassdi 算法通過一種互助的方式，使節點在實現了單向鄰居發現后，能盡快地實現雙向鄰居發現。在這2 種算法思想的基礎上，本文提出了一種基于多信標消息的低時延鄰居發現算法即通過持續廣播快速響應的方式來實現低時延和低能耗的鄰居發現?！俺掷m廣播”是指節點在開始進行鄰居發現時，在一段連續時間內的每個時間段的開始片段廣播一個beacon 消息，該消息中將包含發送節點在這段連續時間之后的第一次蘇醒時刻。而“快速響應”則指發送節點i周圍的節點j在接收到beacon 消息后，主動調整自身下一次beacon 消息的發送時間，從而正好使節點i在蘇醒時刻能夠接收到節點j發送的beacon 消息，實現低時延的雙向鄰居發現。

4.2 算法的詳細設計

ready-go 算法基于TMLL 原則進行設計，即節點可以在任意時間段（包括睡眠時間段和蘇醒時間段）中發送一個beacon 消息，而對應的鄰居節點只能在蘇醒時刻才能接收該beacon 消息。在低占空比網絡中，由于每個節點都擁有自己的占空比，使節點間具有不同的睡眠調度方式，且所有節點的占空比均在同一范圍內。假設節點可以預先獲取所有節點中最小占空比的值，則可以將ready-go 算法分為2 個過程：ready 過程和go 過程。ready 過程如圖2所示，go 過程如圖3 所示。

圖2 ready 過程

圖3 go 過程

在ready 過程中，如果MLDC-WSN 中任意一個節點i在某一時刻t0處蘇醒并進行鄰居發現工作，那么節點i首先需要根據已經獲取的節點占空比最小值Γ計算出需要連續發送beacon 消息的次數。接著，發送節點i在之后的N個時間段內的開始時刻發送一個beacon 消息，尋找自己的鄰居節點。如圖2 所示，假設網絡中節點占空比的最小值為，則節點i將從t0開始的15 個時間段內，在每個時間段的開始時刻發送一個beacon 消息，用于尋找自己的鄰居節點。同時，由于Γ是節點中最小的占空比值，在網絡通信可靠的情況下，在N個時間段內，能夠保證節點i周圍通信范圍內的節點（如j、k、l等）都能收到它發送的beacon 消息。beacon 消息包含發送節點i在N個時間段后的第一次蘇醒時刻t1的信息。

在go 過程中，節點j、k、l在收到鄰居節點i的beacon 消息后，會動態調整自身下一次發送beacon 消息的時間表，以保證在節點i蘇醒的時間段內發送beacon 消息，從而進行雙向的鄰居發現。

為了使示意圖更加清晰，節點占空比設置的值均稍大于實際情況中的占空比值。從圖3 中可以發現，收到節點i發送的beacon 消息的節點j、k、l，會根據beacon 消息中包含的t1時刻的信息，調整自身beacon 消息發送的時刻，使發送的消息正好能被節點i在t1時刻接收到。節點i處理完t1時刻接收到的beacon 消息后，構建在t1時刻的鄰居集合，完成從t0時刻到t1時刻的雙向鄰居發現過程。

此外，考慮到在實際情況中節點間存在一定的時鐘偏移的情況，ready-go 算法通過為每個節點增加一次beacon 消息的發送來進行解決，即節點i在ready 過程中發送N+1 次beacon 消息；同時，節點j、k、l在發送beacon 消息時間段的開始與結束時刻，均發送一個beacon 消息。

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

算法1ready-go 算法

輸入MLDC-WSN 中每一個節點i

輸出每個節點i的鄰居結合Gi

圖4 ready-go 算法示意

4.3 性能分析

4.3.1 節點發現時間表

在ready-go、Nihao 和Griassdi 算法中，每個節點蘇醒的時間和發送beacon 消息的時間是相互獨立的。本節將使用與U-connect 算法中相似的模型來定義ready-go 算法中的發現時間表。

ready-go 算法中節點i的發現時間表被定義為2 個二進制函數：ψL(i,t)和ψB(i,t)，分別代表時刻t的蘇醒時間段和發送beacon 消息的時間段，即

因此，節點之間的鄰居發現可以通過ψL(i,t)和ψB(i,t)來定義。如果節點i和節點j在通信范圍內，那么節點i可以單向發現鄰居節點j，可定義為ψL(i,t)=1，ψB(i,t)=1；如果節點i和節點j在通信范圍內，那么節點i和節點j可以實現雙向發現鄰居，可定義為

即存在時刻t1、t2，使在t1時刻，節點i處于蘇醒時間段，節點j處于beacon 消息發送時間段；在t2時刻，節點i處于beacon 消息發送時間段，節點j處于蘇醒時間段。

在ready-go 算法中，節點的發現時間表可以定義為

其中，τi表示節點i的蘇醒時刻占空比，τmin表示節點蘇醒時刻占空比的最小值，T表示節點i的工作周期，n表示節點i在一個工作周期中的第n+ 1次蘇醒，t1表示節點i在連續發生beacon 消息之后的第一次蘇醒時刻。

在Nihao 算法中，節點的發現時間表可以定義為

其中，L表示Nihao 算法中節點的最壞發現時延，為節點的工作周期長度，即L=T=mn；[t]L表示t對L取模，[t]L＜m表示節點每個工作周期的前m個時間段，ma表示第a個m長度。

4.3.2 占空比時延乘積模型

通信能耗（Ecost）和發現概率（P）是低占空比傳感網中鄰居發現的重要衡量指標。將節點在一個工作周期內的數據接收/發送的數據量與傳輸1 bit 數據的平均能耗的乘積作為該節點的通信能耗，即

其中，DC 為節點一個工作周期內的占空比值，T為節點的工作周期，H為節點發送/接收1bit 數據的平均能耗，B為傳輸帶寬。

由文獻[17]可知，節點i在時間t內被動蘇醒發現鄰居節點k的概率為

針對式(8)，對于任意給定的節點，T×H×B通常為一個常數c，即Ecost=cDC ；針對式(9)，可以通過計算概率密度函數獲得任意節點i發現所有鄰居節點的期望時延，即

經上述分析可以發現，占空比和發現概率分別是影響節點通信能耗和發現時延的關鍵因素，使占空比和最壞情況發現時延已經成為衡量鄰居發現算法優劣的重要指標。

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

其中，Nc為在一個工作周期中節點蘇醒時發送beacon 消息的時間隙個數，即是為了避免重復計算beacon消息發送個數；α為節點發送一個beacon 消息所需時間段長度的比例。

在WSN 中，節點的發現時延和通信能耗往往是一對對立的指標，更低的時延意味著更多的能耗。為了方便比較算法性能，文獻[11,15-16]提出了將占空比與時延的乘積作為評價鄰居發現算法性能的指標。如果2 個指標都小，則它們的乘積也小，算法性能更好。文中采用同樣的評價模型將ready-go 算法與其他典型的鄰居發現算法進行性能對比，占空比和時延乘積Λ為

其中，L表示最壞情況下的節點鄰居發現時延。

下面將給出ready-go 算法與Nihao 算法的DC值與L值，在ready-go 算法中，節點的最壞發現時延L可以表示為

節點的占空比DC 可以表示為

在 Nihao 算法中，節點的最壞發現時延L=T=mn，節點蘇醒時刻的占空比，則占空比DC 為

因此，Nihao 算法的占空比時延乘積為

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

則ready-go 算法的占空比時延乘積為

經過上述分析，可以發現，當n＞ 2時，有DCready-go＜ DCNihao且Lready-go＜LNihao，即ready-go 算法在占空比和最壞情況下的發現時延都小于Nihao 算法，使Λready-go明顯優于ΛNihao。實際上，當τ i＞τmin時，ready-go 算法可以得到更優的最壞情況下節點發現時延值，以實現更低的占空比和時延乘積。

4.3.3 占空比時延乘積對比

將本文所提的ready-go 算法與前文提到的典型鄰居發現算法的占空比時延乘積進行對比。根據算法類型的不同，在計算中節點占空比和最壞情況下發現時延時，各算法盡可能使用相同的參數，具體對比情況如表1 所示。

表1 典型算法的占空比時延乘積對比

表1 中，n為C-tours quorum 算法中節點的工作周期的長度；p1、p2為Disco 算法中選取的2 個素數，節點隨機選取2 個素數之一作為自己的工作周期；T=q2為U-connect 算法中節點的工作周期；為Searchlight 算法中節點的工作周期，即將節點的工作周期分解成一個寬是高兩倍的矩陣；Nihao 算法中，節點工作周期為T=mn，m、n根據具體的網絡場景調整，m表示節點連續蘇醒的時間段個數，n表示節點beacon 消息發送的次數；ready-go 算法中，m等價于節點的工作周期T乘以節點的蘇醒時刻占空比τi，

4.3.4 多信標平均能耗

在TMLL 模型中，節點發送beacon 的時刻與節點的蘇醒時刻是相互獨立的。假設每個節點在一個工作周期內的蘇醒時間段都相同，由式(10)可知，節點在睡眠時間段發送 beacon 消息的能耗為節點在蘇醒時發送信標的能耗為αwNc，則節點在一個工作周期中發送beacon 消息的能耗為

其中，B為節點的傳輸數據帶寬，|T|為一個工作周期中的時間段個數。

由于節點發送beacon 消息的時隙只占一個時間段中的極少一部分。結合式(10)和式(18)可得，Cnon_beacon?Cbeacon，其中Cnon_beacon為節點在一個工作周期內其余工作的能耗（即Cnon_beacon=aB(ψL(i,t)-Nc)）。因此，在實際應用中，可以通過對多個工作周期內節點睡眠時刻發送beacon 消息的能耗和蘇醒工作時的能耗進行累加，求取平均能耗來替代節點的多信標平均能耗。

5 實驗及對比分析

本節通過實驗仿真來測試ready-go 算法的性能，并將該算法的實驗數據與前文提到的幾種典型算法的數據進行對比。為了降低實驗誤差造成的影響，每組實驗進行1 000 次，數據取平均值。

5.1 實驗環境

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

圖5 WLDC-WSN 分布示意

5.2 性能表現

本節分別從限定時延的發現概率、節點最壞情況下的發現時延、網絡平均能耗等方面進行了測試，并將ready-go 算法與其他典型鄰居發現算法進行了對比。

5.2.1 限定時延的發現概率

在這組實驗中，根據4.3.2 節的發現概率模型，設定節點蘇醒占空比為1.4%。在給定限定時延發現概率的情況下，測試了ready-go 算法的數據，并與SPND、Nihao、Griassdi 這3 種算法的限定時延發現概率進行了對比，結果如圖6 所示。

圖6 限定時延的發現概率

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

經過上述對比可知，ready-go 算法由于采用了持續廣播快速響應的思想，使節點能在最短的時間內找到所有的鄰居節點，這使它的限定時延發現概率的收斂速度優于其他3 種算法。

5.2.2 節點最壞發現時延

在這組實驗中，通過取節點蘇醒占空比值的范圍為0.2%～1.4%，測試了節點發現所有鄰居節點的發現時延，實驗結果如圖7 所示。

圖7 不同占空比下的發現時延

從圖7 中可以發現，隨著節點蘇醒占空比值的增大，SPND 算法的最壞發現時延明顯大于其他3種算法的最壞發現時延，ready-go 算法和Griassdi算法能取得較小的最壞發現時延。同時，ready-go算法與其他算法相比，在所有占空比取值情況下都能取得最低的最壞發現時延。因此，經過實驗對比可知，采用共享蘇醒時刻策略的ready-go 算法，可以使本該處于睡眠狀態的節點動態調整自身蘇醒的時刻，從而增大了蘇醒狀態收到beacon 消息的概率，降低了最壞發現時延。

5.2.3 網絡平均能耗

在網絡能耗的測試中，每次選取網絡中任意一個節點進行測試以評估網絡能耗，并通過多次測試取平均值來減少實驗誤差。首先，設置節點的傳輸帶寬為B=256 kbit/s，則節點發送一次beacon 消息的數據量為Sbeacon=Bα。

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

圖8 節點平均能耗

6 結束語

本文提出了一種基于多信標消息的低時延鄰居發現算法ready-go。該算法通過獲取網絡中節點蘇醒占空比最小值，計算出持續發送beacon 消息的次數；節點在開始進行鄰居發現工作時，持續發送多個beacon 消息，保證周圍的潛在鄰居節點都能收到，并通過調整自身beacon 消息的發送時刻，從而快速實現雙向的鄰居發現。理論分析和仿真實驗表明，ready-go 算法與其他典型算法相比，能獲得更小的鄰居發現時延。同時，節點能夠實現限定時延的發現概率比現有典型算法的收斂速度更快。