移動低占空比無線傳感網中低能耗的主動鄰居發現算法

梁俊斌，周翔，李陶深

（廣西大學計算機與電子信息學院廣西多媒體通信與網絡技術重點實驗室，廣西 南寧 530004）

1 引言

移動低占空比無線傳感網（MLDC-WSN,mobile low-duty-cycle wireless sensor network）是近年出現的一種新型自組織網絡。它與傳統的無線傳感器網絡（WSN,wireless sensor network）一樣，由大量能量、通信范圍、存儲容量和計算能力均有限的節點組成，主要部署在人類無法進入的惡劣環境中，從事長期的監測或跟蹤任務[1,2]。但是，它與WSN有明顯的區別：WSN中節點是靜止且保持蘇醒的，而MLDC-WSN中的節點會長時間進入睡眠狀態以保存能量，僅在少量時刻蘇醒并通過移動來執行任務[3]。因此，MLDC-WSN的拓撲變化會更加頻繁，導致節點鄰居也不時地發生改變。

鄰居發現是網絡中的一個重要的操作，網絡中的節點需要快速地相互發現，才能自組織形成網絡。由于鄰居發現在移動的網絡中需要周期性多次執行，因此，以較小的能耗實現快速的鄰居發現，是網絡能正常開展工作及延長生命周期的重要保障[4,5]。在MLDC-WSN中，節點采用低占空比工作模式（即節點在每個工作周期中的大部分時間處于睡眠狀態，僅在少量時刻蘇醒），而節點間的鄰居發現又要求節點同時處于蘇醒狀態，使節點等待被發現的鄰居蘇醒所需要的時間很長，造成巨大的時延。此外，節點蘇醒時的移動會導致網絡拓撲結構不斷改變，使節點的鄰居也會不時發生變化。因此，實現低時延、低能耗的鄰居發現非常困難。

目前，已有的典型工作是采用節點主動蘇醒的方式來進行鄰居發現，但是這種方式要求節點多次主動蘇醒，從而耗費較多的能耗。如何減少主動蘇醒的次數、降低能耗，同時快速地完成鄰居發現，仍然是一個亟待解決的難題。

本文提出了一種新的低能耗的選擇性主動蘇醒鄰居發現（SPND,energy saving selectively proactive neighbor discovery）算法。在SPND算法中，節點能夠結合網絡中節點的移動模型，根據集合的劃分，選擇性地在鄰居蘇醒的時刻同時蘇醒，與鄰居節點進行確認。例如，節點i在某時刻已經擁有了自身的鄰居集合，網絡中節點經過一段時間的移動后，某些節點已經不再是節點i的鄰居。在下一時刻，節點i只需選擇性地主動蘇醒發現那些可能成為自身鄰居的節點。

2 相關工作

根據喚醒調度模式的確定性，鄰居發現算法可以分為概率性鄰居發現和確定性鄰居發現。在確定性鄰居發現算法中，根據節點是否主動蘇醒發現鄰居，又可以進一步劃分為主動式鄰居發現和被動式鄰居發現。

2.1 概率性鄰居發現

概率性鄰居發現算法采用隨機喚醒的調度方式，通過設置節點在每個時間片所處狀態的概率，可以獲得較低的平均發現時延，但是最壞情況下發現時延可能會非常大。Mcglynn等[6]提出了一種典型的概率性鄰居發現算法 Birthday，它利用生日悖論的概率性原理，即在隨機抽取n個人組成的集合中，當n很大時，有人生日在同一天的概率會很大。因此，節點以某種概率來選擇當前時隙節點的狀態（包括睡眠、發送、偵聽），通過細致地設置各個狀態的概率值，節點在一段連續時間內會有很高的概率可以相互發現。該算法能夠實現鄰居發現過程中能量消耗和發現時延之間的良好平衡，但它無法限定最壞情況下的發現時延。針對這個問題，You等[7]提出了 ALOHA-Like 算法，它分析任意節點發現n-1個鄰居節點的期望時間，有很高的概率能限定最壞情況下的發現時延。

2.2 確定性鄰居發現

確定性鄰居發現中，節點采用固定的喚醒調度模式，即節點處于睡眠或蘇醒狀態按照預定的睡眠蘇醒調度表周期性地重復。

2.2.1 被動式鄰居發現

被動式鄰居發現算法是指節點完全按照預定的蘇醒時刻蘇醒進行鄰居發現。一個典型的被動式鄰居發現算法是 Jiang等[8]提出的 TQS（torus quorum system）鄰居發現算法。該算法將節點工作周期編排成t×w矩陣，工作周期長度為n=t×w。節點任選其中一列 c的所有元素，再從所選)列任意位置選擇個元素，作為節點的蘇醒時間片。TQS能實現較優的能耗時延指標，但是不適用于每個節點采用不同的喚醒調度模式的情況。為了解決這個問題，Zheng等[9]實現了一種不需要時隙對準的異步蘇醒協議（AWP,asynchronous wakeup protocol）算法，該算法中節點可以根據其在網絡中的不同角色靈活設置占空比。AWP將鄰居發現問題簡化為一個圖的最小頂點覆蓋問題，而解決圖的最小頂點覆蓋問題都是集中式的方法，但集中式的方法在節點分散的無線傳感網中并不適用。

針對TQS算法及AWP算法的不足，Dutta等[10]提出了 Disco算法。Disco算法中每個節點選擇 2個素數作為其工作周期，節點大部分時間處于睡眠狀態，每個節點擁有一個獨立的計數器，一旦節點計數器能夠整除其任何一個素數工作周期，使該節點處于蘇醒狀態。根據中國剩余定理[11]，2個節點的蘇醒時隙必然能夠周期性地重疊或部分重疊，Disco算法能夠確保一直在鄰居范圍內的2個節點能夠在一定的時限內相互發現。

為了統一解決節點喚醒調度模式異步和同步的問題，Kandhalu等[12]提出了U-Connect鄰居發現算法。U-Connect算法選擇素數q作為其基本工作周期，然后，在連續T個時隙內構建q×q的網格矩陣（T=q×q），并在矩陣內任選某列和某行的一半時隙作為節點的蘇醒時隙，當該行后面的時隙數不足一半時，返回到該行的首列繼續選擇。U-Connect算法融合了中國剩余定理和 TQS算法的思想。U-Connect算法的能耗—時延指標是最優理論系統的1.5倍左右，在能耗時延均衡方面優于TQS算法和Disco算法。

2.2.2 主動式鄰居發現

已有的鄰居發現算法有很多，但是它們都基于節點被動式蘇醒進行鄰居發現。Chen等[13]提出了一種節點主動蘇醒的鄰居發現算法Q-connect。該算法分析了節點從睡眠狀態切換到蘇醒狀態所需的能耗，考慮到該部分能耗不可忽視，Q-connect 算法將節點時間片細分為幾個部分，在第一部分主動蘇醒廣播 beacon 消息，在第四部分主動蘇醒接收beacon 消息。Q-connect 算法能提高網絡的能效利用率，但是節點平均發現時延較大。

為了充分利用beacon 消息減少發現時延，Qiu等[4]提出了一種主動式的鄰居發現算法 Nihao。Nihao算法基于“多說少聽”（TMLL,talk more listen less）的原則，節點在一個周期（m×n）的前 m 個時間片處于“聽”（蘇醒）狀態，并在整個周期中每隔 m個時間片進入“說”（主動蘇醒發送一個beacon消息）狀態，即一共發送n個beacon消息。在Nihao算法中，beacon消息可以在節點睡眠狀態主動蘇醒發送，因此，使節點在較少時間片內相互發現，減少發現時延。

Kindt等[14]提出了一種主動式鄰居發現算法Griassdi。在Griassdi算法中，節點周期性地蘇醒與發送beacon消息，且蘇醒與beacon消息的發送相互獨立。節點在某個時間片內蘇醒收到其他節點的beacon消息后，會根據其他節點的下一次蘇醒時間，調整自身下一次發送beacon消息的時刻，以實現快速與其他節點相互發現。

這部分算法都要求節點在一個時間片的部分時刻發送beacon消息，Chen等[15]提出了一種不需要發送beacon消息的節點主動蘇醒發現鄰居GBD（group-based discovery）算法。在 GBD 算法中，相互發現的節點位于一個組中。組中的節點根據移動低占空比網絡的時空特性，選擇性地將它們部分現有鄰居的睡眠和蘇醒時刻分享給新發現的加入組中的鄰居節點。新發現的節點就能快速地獲得周圍節點的蘇醒時刻表，在周圍節點蘇醒的時刻主動蘇醒，從而判斷2個節點是否是鄰居。針對節點密度較大的網絡，Chen等[15]又對GBD算法進行改進，提出了AGBD（advanced group-based discovery）算法。在AGBD算法中，節點遵循一個基于移動網絡時空特性的選擇機制，這種機制能減少節點部分不必要的主動蘇醒，但是可能會漏掉鄰居節點。GBD算法的優點是平均發現時延較低，節點能在潛在的鄰居節點蘇醒時主動蘇醒進行鄰居發現，減小了網絡低占空比特性增大的發現時延。但是，GBD算法存在2個方面的不足。

1) 節點選擇性地主動蘇醒進行鄰居發現，無法限定最壞情況的最大發現時延。

2) 節點基于概率的選擇性轉發會降低節點發現鄰居的可靠性。

以上是針對低占空比網絡的一些典型鄰居發現算法，可以發現，概率性鄰居發現算法能取得較低的網絡能耗且以較小的時間發現大部分鄰居，但是無法限定最壞情況下的全網最大發現時延。確定性鄰居發現中，被動式鄰居發現算法時延往往較大，主動式鄰居發現算法能取得較小的發現時延，但是需要節點主動蘇醒或主動發送beacon消息，網絡能耗較大。本文將針對這些算法的優缺點進行建模，并提出優化的解決方案。

3 系統模型和問題描述

本節將給出MLDC-WSN的網絡模型及本文研究問題的描述，同時對相關術語進行定義。

3.1 相關定義

定義1 通信半徑[16]。節點以一定功率通信能保障消息被其他節點接收到的最遠距離。

定義2 節點的發現概率[17]。距離在通信范圍內的2個節點能相互發現的概率。

定義3 節點的發現比率[17]。網絡的任意節點發現的鄰居節點數目占所有通信范圍內節點數目的比率。

定義4 發現時延[17]。從節點移動到通信范圍內的時刻開始到它們相互發現時的時間間隔。

3.2 網絡模型

假設一個擁有n個移動節點的無線傳感器網絡Gnet={V,E}，其中，V表示網絡中節點的集合，E表示網絡中節點間是否連通的信息。Gnet中節點采用低占空比工作模式，將移動節點的工作狀態定義為睡眠（sleep）—蘇醒（active）狀態，如圖 1所示，即節點大部分時間處于 sleep狀態，關閉除去定時器以外所有其他功能模塊，只在少部分時間，如第3、12個時間片處于active狀態，感知數據和通信。節點能在任何時候主動蘇醒發送數據分組，但是只能在計劃的蘇醒時刻接收數據分組。

圖1 占空比示意

為了考慮網絡分布較為均勻的情況，網絡的節點采取 Random Waypoint移動模型。在 Random Waypoint移動模型[18]中，每個移動節點隨機選取一個方向作為目標方向，然后選定一個范圍在[0,vmax]的恒定速度v移動，其中，vmax為節點能移動的最大速度。節點間方向及速度的選取相對獨立。網絡中節點在特定的時間段Δt內移動，節點在一個Δt時間段內移動的距離范圍為[0,vmax×Δt]。

3.3 問題描述

網絡中的節點i與節點j能在某個時刻t實現相互發現需要滿足2個條件。

1) 在某個時間段Δt內，節點i與節點j在通信范圍內，假設網絡中節點的通信半徑一致為R。

2) 節點i與節點j在Δt內同時處于蘇醒狀態，且Δt不小于節點實現鄰居發現所需的最小時間。

節點間同時滿足以上2個條件，才能被稱為節點i與節點j能在[t,t+Δt]實現相互發現。

在MLDC-WSN中，節點的鄰居發現時延是指從2個節點可以相互通信的時刻t0開始，到它們完成相互發現的時刻t+Δt為止的時間間隔δ，即

節點的發現概率是指在通信范圍內的2個節點i和節點j能相互發現的概率Pij，Pij的取值范圍為[0,1]。Pij(t)=0表示節點在t時間內無法相互發現，Pij(t)=1 表示節點在t時間內肯定能相互發現。用比率Pi(t)表示節點i在t時間內發現的鄰居節點占所有通信范圍內鄰居的比率。因此，MLDC-WSN中鄰居發現問題可以歸納為以最小的能耗實現發現時延δ的最小化與以最小的時間實現發現比率Pi的最大化問題，即

其中，δ=t+Δt-t0，由于Δt通常是常量無法調節，只有t-t0可以通過算法進行優化。在已有的能實現較低發現時延的算法中，通常無法使P接近1。本文提出一種新的節點主動式鄰居發現算法SPND，能實現低能耗的快速鄰居發現，以下是其詳細的描述。

4 算法設計

本節將給出 SPND算法的基本思想及詳細設計，并從理論上將SPND算法和已有的鄰居發現算法進行對比。考慮到已有的典型算法采用了節點的主動蘇醒來減小鄰居發現時延，SPND算法專注于結合網絡移動性模型，減少節點主動蘇醒次數，從而實現低能耗的主動式鄰居發現。

4.1 算法基本思想

在SPND算法中，對于剛部署的傳感器網絡，每個節點分布式地開展鄰居發現工作。針對移動傳感器網絡的特點，將節點的鄰居發現分為2步。步驟1根據基于組的鄰居發現算法構建節點初始鄰居集合，依據這樣一個原則：新加入組中的鄰居節點將自身的鄰居集合信息分享給組中的其他節點，組中的其他節點就能快速地獲取潛在的鄰居節點的蘇醒時間，從而在該時間主動蘇醒進行鄰居發現。步驟2結合節點的移動模型，選擇性地指定節點的主動蘇醒時刻，節點主動蘇醒發現該時刻的鄰居集合，依據這樣一個原則：網絡中節點經過一段時間的移動后，節點只選擇那些移動后可能在通信范圍內的潛在鄰居節點進行主動式蘇醒的鄰居發現；將肯定在鄰居范圍內的節點按既定的睡眠蘇醒狀態進行鄰居發現；將肯定移動出鄰居范圍內的節點剔除出鄰居集合。

4.2 算法詳細設計

SPND算法分為2個階段。網絡剛部署，構建節點初始鄰居集合為第一階段。選擇性地指定節點的主動蘇醒時刻，節點主動蘇醒發現該時刻的鄰居集合為第二階段。網絡中的節點分布式地完成第一階段的鄰居發現過程，然后節點間完全異步地從第一階段切換到第二階段。

4.2.1 構建初始鄰居集合

MLDC-WSN部署后，首先在t時刻，網絡中任意一個節點i分布式地生成自己的鄰居集合中節點個數為1時，節點i將依次在自己的蘇醒時刻發送廣播消息來發現鄰居，直到在某個時刻發現了第一個鄰居節點k，并將節點k加入集合中，此時，節點i的集合= {i,k}中節點個數為2。當Gi≥ 2 時，如圖2所示，節點i按以下步驟進行下一步的鄰居發現。

圖2 構建初始鄰居集合

1) 網絡中的每個節點在蘇醒時刻會廣播一個消息，告知網絡自己的存在。如圖2所示，在某個時刻t0，節點i與節點j在通信范圍內，收到了彼此的廣播消息，即節點i和節點j相互發現成為鄰居節點并能獲取彼此的睡眠蘇醒時刻表。

2) 節點j將在節點i的下一次蘇醒時刻t1主動蘇醒，將已經位于Gj中的鄰居節點的睡眠蘇醒時刻表信息發送給節點i。節點i則會在節點j的下一次蘇醒時刻t2將已經位于Gi中的鄰居節點（如節點k）的睡眠蘇醒時刻表信息發送給節點j。

3) 節點j在收到節點i的鄰居信息后，將依次在節點i的鄰居節點（如節點k）的下一次蘇醒時刻t3主動蘇醒，然后發送消息，來確認該節點是否是節點j的鄰居。節點i以同樣的方式確認節點j的鄰居是否是節點i的鄰居。

具體算法如算法1所示。

算法1 構建初始鄰居集合

1) for (網絡中每一個節點i) {

2) while (t＜T) {

3) if (節點i蘇醒發現節點h) {

4) 節點i和節點h共享G;

5) } else {節點i睡眠}

6) if (節點h的鄰居蘇醒) {

7) 節點i主動蘇醒;

8) 節點i與節點k確認;

9) } } }

每當節點i的鄰居集合Gi加入新的鄰居節點，循環執行與新加入節點的鄰居進行確認的步驟，即算法 1中的步驟 6)～步驟 8)，直到收到的所有鄰居信息都被確認完畢，完成第一階段的初始鄰居集合構建。

4.2.2 選擇性指定蘇醒時刻

節點構建完初始鄰居集合即進入第二階段的鄰居發現工作，即當節點i周圍有節點移動后，為節點i選擇性地指定其后主動蘇醒進行鄰居發現的時刻。網絡中節點采用Random Waypoint移動模型，即節點每次移動的最大距離為ΔS=vmax×Δt，方向隨機。在網絡中，假設節點的通信半徑一致為R。節點i在某個時刻t的鄰居集合為，經過一段時間Δt的移動后，節點i的新鄰居集合為。如圖3所示，根據網絡模型可知，中與節點i的距離在[0,R-ΔS)范圍內的節點肯定在中，與節點i的距離在[R+ΔS,+∞)范圍內的節點肯定不在中，距離在[R-ΔS,R+ΔS)范圍內的節點可能在中。因此，對于節點i而言，在經過Δt時間移動后，下一次進行鄰居發現時，可以只需考慮距離在[R-ΔS,R+ΔS)范圍內的節點。

圖3 節點移動示意

傳感器網絡中，節點可以通過 RSSI信號強度來大致估計互為鄰居的節點間的距離。對于已經獲取了鄰居集合的節點i而言，如圖4(a)所示，可以根據節點間的距離將鄰居集合劃分為 2個子集合和。其中，集合中節點k具有的性質是節點k與節點i之間的距離lik在[0,R-ΔS)范圍內。集合中節點h具有的性質是節點h與節點i之間的距離lih在[R-ΔS,R+ΔS)范圍內。

圖4 集合劃分示意

對于在集合[R,R+ΔS)范圍內的節點g，可以通過節點h來獲取。如圖4(b)所示，令r=R+ΔS-lih，節點h位于集合內，并且擁有自己的鄰居集合，則需要將集合中與節點h距離在[0,r]范圍內的鄰居節點的信息發送給節點i，構建節點i的鄰居集合。具體算法如算法2所示。

算法2 集合劃分與確認鄰居節點

1) for (網絡中每一個節點i) {

2) if (節點i的鄰居集合Gi非空) {

3) for (集合Gi中任意節點j){

4) if (節點i和節點j的距離＜R-ΔS){

6) }else if (R-ΔS＜節點i和節點j的距離＜R+ΔS) {

8) }}

11) }

13) 節點i主動蘇醒與節點l確認;

14)} } }

4.3 理論分析

針對發現時延，將SPND與已有的典型算法進行對比，并分析SPND算法的能耗和發現概率。首先，從理論上定性地證明SPND算法發現時延優于已有的被動式蘇醒鄰居發現算法，然后定量地比較節點發現所有鄰居節點時延的期望值。

4.3.1 發現時延分析

假定一對已經相互發現的鄰居節點i和節點j，節點 i的鄰居集合中包含節點 k，下文分析節點 j發現節點k的時延。為了簡化問題模型，假定節點j與節點k在一個周期開始之前恰好移動到通信范圍內。設集合C為節點j和節點k可能的發現時間集合，當節點i與節點j以被動式的蘇醒進行鄰居發現時，則有 C =τj∩τk，即節點j與節點k的最小發現時延為min C。當采用SPND算法構建節點初始鄰居集合時，節點j能通過節點i提前獲取節點k的蘇醒時刻，主動蘇醒進行鄰居發現，即會增加節點j的工作模式τj中的蘇醒時間片。節點j新的工作模式為τ′j，則有C因為 τj? τ ′j，則有C?C′。即選擇性主動蘇醒鄰居發現算法的發現時延小于或等于傳統的被動式蘇醒鄰居發現算法的發現時延。

不失一般性地，本文選取 Disco算法作為定量比較的對象。與其他被動式蘇醒算法U-connect和 Searchlight一樣，Disco算法中網絡中的每個節點在網絡部署前規劃好自身的睡眠蘇醒時刻表，網絡部署后，節點按時刻表蘇醒進行鄰居發現。其特性是能限定節點 j和節點 k發現的最大時延即當節點 j與節點 k在通信范圍內的時間時，肯定能相互發現。當時，節點j和節點k能相互發現的概率為p=f(j,k,t)。即節點j與節點k在t時間內相互發現的概率可以表示為

則節點j采用Disco算法在t時間內發現所有n-1鄰居節點的概率可以表示為。它的密度函數可以表示為

通過概率密度函數計算節點j發現所有鄰居節點的期望時間為

當采用SPND算法構建節點初始鄰居集合時，節點i被動蘇醒，在時間t內發現通信范圍內第一個鄰居節點j的概率(t)可以表示為

它的概率密度函數為

通過概率密度函數計算節點i發現所有鄰居節點的期望時間為

其中，max(Th)是節點h的連續2個蘇醒時間最大間隔。節點 i以(t)的期望時間發現第一個鄰居節點后，最多還需要2max(Th)的時間來進行鄰居確認和分享自身的鄰居集合信息。第5節將通過仿真實驗，比較Disco算法的期望發現時延和SPND算法的期望發現時延。

4.3.2 蘇醒及主動蘇醒次數分析

節點用于鄰居發現的蘇醒時間片主要包括2個部分：按既定的睡眠蘇醒時刻表上蘇醒的時間片和主動蘇醒的時間片。在SPND算法中，節點j通過鄰居節點i獲取了節點i的鄰居后，通過增加節點j的工作模式τj中的蘇醒時間片進行鄰居發現，能減小發現時延，增大發現概率。為了減少增加的蘇醒時間片帶來的能耗，本文設計了選擇性地指定節點主動蘇醒時刻。

假設網絡中節點一致分布，密度為 ρ，即網絡在單位面積的范圍內擁有ρ個節點，則在節點i周圍距離R范圍內平均有 Ni=πR2ρ個節點。現有的節點主動式蘇醒的算法中，節點i需要主動蘇醒發現在集合、和中的所有潛在鄰居節點，即平均主動蘇醒= π (R+Δ S)2ρ次。在本文設計中，節點i只需主動蘇醒發現在集合和中的所有潛在鄰居節點，即平均主動蘇醒次數為

節點i可以減少約φ次的主動蘇醒次數，φ表示為

其中，ΔS是網絡中節點一次移動的最大距離，可見在ΔS不為0的情況下，節點i能減少的蘇醒次數是很可觀的一部分。

4.3.3 能耗分析

無線傳感器網絡中節點的能耗 En主要包括 3個部分：處理器模塊的能耗 Ep、通信模塊的能耗Ec和感知模塊的能耗Es。處理器模塊有3個工作狀態，分別是運行態（run）、空閑態（idle）和睡眠態（sleep）。通信模塊一般有 6種狀態，分別是發送（send）、接收（recv）、關閉（off）、空閑（idle）、睡眠（sleep）和信道檢測評估（CCA/ED）。感知模塊則只有開（on）、關（off）2種狀態。在評估網絡鄰居發現能耗時，可以認為感知模塊獨立于其他 2個模塊，因此，本文評估 SPND算法能耗 En-SPND時主要考慮處理器模塊與通信模塊的能耗，即

在節點蘇醒及主動蘇醒的時間片內，處理器可能處于運行態或空閑態，運行態處理器一個時間片內正常執行指令需要消耗能量Ep-run，空閑態部分功能暫停執行，能耗 Ep-idle相對較小。通信模塊則可能處于發送、接收或信道檢測評估狀態。在節點處于睡眠狀態時，處理器模塊與通信模塊也都處于睡眠態，此時節點的大部分模塊關閉，系統能耗Ep-sleep、Ec-sleep最小。

根據文獻[12]可知，節點在一個蘇醒狀態時間片內進行信道檢測評估的能耗Ec-CCA/ED和收發數據需要的能耗Ec-send、Ec-recv基本相等。即節點在蘇醒及主動蘇醒的時間片內，通信模塊消耗Ec的能量是一定的，處理器模塊根據處于運行態與空閑態的不同，能耗有差異，但都大于節點處于睡眠態的處理器模塊能耗Ep-sleep。

因此，本文將SPND算法的能耗En-SPND模型定義為節點處于蘇醒及主動蘇醒的次數N與節點每個時間片內蘇醒的能耗En的乘積，然后加上節點處于睡眠狀態的能耗，即

其中，N表示節點蘇醒及主動蘇醒次數，NS表示節點處于睡眠的時間片個數。Nrun表示N中處理器模塊處于運行態的次數，Nidle表示N中節點處理器模塊處于空閑態的次數。Ec表示通信模塊進行一次收發數據或信道檢測評估能耗的均值。Ec-sleep表示通信模塊一個時間片內處于睡眠的能耗。

4.3.4 發現概率分析

現有的主動式蘇醒算法中，GBD算法能實現時延、能耗較優的鄰居發現，本文將與該算法比較節點i發現所有鄰居的概率。在GBD算法中，節點i根據節點間的距離lik和lij判斷是否在節點k的蘇醒時刻主動蘇醒，其中，k是節點j的鄰居。計算節點k是節點i的鄰居的概率式為

通過為Pj,ik(ljk,lij)設置不同的臨界值來判斷節點i是否主動蘇醒發現節點k。該算法僅通過概率來判斷是否主動蘇醒進行鄰居發現，這會導致節點i可能主動蘇醒發現不在鄰居范圍內的節點，也可能錯過主動蘇醒發現鄰居范圍內的節點，造成節點i在t時間內發現所有鄰居節點的概率Pi(t)較小。

在SPND算法中，節點i的3個子集合、和中,的節點在t+Δt時刻仍然是節點i的鄰居，通過被動式蘇醒可以發現。和中的節點在t+Δt時刻可能是節點i的鄰居，通過主動式蘇醒可以發現，即節點i能發現3個子集合、和中所有鄰居節點。需要注意的是，在實際網絡情況下，由于存在分組丟失率、節點移動可能頻繁或速度較快、子集合可能無法獲取[R,R+ΔS)范圍內的所有節點等問題，造成節點i無法在t+Δt時刻發現所有鄰居節點。但是這些假設的存在只會影響SPND算法的性能，不會改變SPND算法發現概率高的可靠性。

5 實驗及分析

本文通過仿真實驗測試SPND算法性能，并將SPND算法的實驗數據與已有的典型算法的數據進行對比。為了減少實驗誤差造成的影響，每組實驗進行1 000次，數據取平均值。

5.1 實驗環境

本文使用C++語言搭建了一個仿真平臺，然后在該平臺上分別實現了SPND算法與Disco、GBD、Birthday這3個對比算法的仿真。在仿真中，假設網絡部署在1 000 m×1 000 m的范圍內，由完全隨機分布的500個移動低占空比節點組成。所有節點均在網絡部署區域范圍內移動，且節點的移動采用Random Waypoint 移動模型。節點默認的平均移動速度為1 m/s，在1±0.3 m/s范圍內隨機取值，即節點最大移動速度為1.3 m/s，最小移動速度為0.7 m/s。節點的占空比設置為5%，表示節點每20個時間片將會有一個時間片處于蘇醒狀態，其他時間片處于睡眠狀態。網絡中節點的默認通信半徑一致為100 m。網絡中節點鄰居信息的TTL（即鄰居信息失效的時間）設置為5 000個時間片，每個時間片為10 ms。這個設定是合乎實際場景的，例如，一個 CC2420無線傳感器節點收發1 B的數據大約需要0.032 ms，因此，在網絡完全異步的情況下，10 ms的時間片也能在極大限度內保證2個節點能在一個同時蘇醒的時間片內完成鄰居發現工作。

5.2 性能表現

本文分別測定了網絡平均發現時延、節點蘇醒次數、節點能耗及限定時延內的節點發現比率這 4個方面的數據，通過這4組仿真實驗數據進行SPND算法與其他算法的對比分析。

5.2.1 網絡平均發現時延

本節測定了不同網絡占空比和節點移動速度情況下網絡的平均發現時延。首先測定了網絡中每個節點發現所有鄰居節點的發現時延，然后取所有節點發現時延的平均值作為整個網絡的平均發現時延。設置網絡節點移動速度為1 m/s，占空比從1%到10%，得到占空比不同的發現時延如圖5(a)所示。設置網絡中節點占空比為3%，移動速度從1 m/s到10 m/s，得到移動速度不同的發現時延如圖5(b)所示。

圖5 網絡平均發現時延

由圖5(a)可以發現，隨著節點占空比的增加，節點擁有更多的蘇醒時間片進行鄰居發現，能減少節點的鄰居發現時延。當節點占空比達到0.05及以上時，SPND算法能實現10 s以內的鄰居發現時延。由圖5(b) 可以發現，隨著節點移動速度的增大，所有算法的發現時延均有一定程度的減小。這是因為節點移動速度增大，造成節點在通信范圍內的時間減少，節點能發現的鄰居節點數目也就較少，因此節點發現時延減小，整個網絡的平均發現時延隨之減小。

5.2.2 節點蘇醒次數

本節主要測定了不同占空比和移動速度情況下節點發現所有鄰居節點需要的蘇醒次數。這里的蘇醒次數包括有節點按睡眠蘇醒時刻表被動蘇醒的次數以及節點根據鄰居集合信息主動蘇醒的次數，得到仿真實驗數據如圖6所示。由圖6可知，SPND算法中節點主動蘇醒平均次數占節點總蘇醒平均次數不到30%，帶來的額外能耗優于已有的主動蘇醒鄰居發現算法。

圖6 節點蘇醒次數

由圖6(a)可以發現，在節點占空比增大時，節點的總蘇醒次數會減小，而節點的主動蘇醒次數基本保持穩定。這是因為節點占空比的變化不影響節點在某個時刻需要發現的鄰居節點的數目，而較大的占空比使節點擁有更多的被動蘇醒時間，因此，總蘇醒次數會減小。由圖 6(b)可以發現，在節點移動速度增大時，節點主動蘇醒次數會先增加后持平，總蘇醒次數也隨之增加。這是因為增大的移動速度會使節點周圍鄰居集合變化快，節點需要更多的主動蘇醒時間發現新的鄰居節點。而當節點速度增大到一定程度，使節點在通信范圍內的時間不足以進行鄰居發現工作，節點主動蘇醒次數就保持穩定。

5.2.3 節點能耗

本節將展示SPND算法的網絡能耗，并與現有的主動式鄰居發現算法 GBD進行對比。在此處的網絡能耗中，仿真實驗考慮了與節點鄰居發現相關的處理器模塊的能耗和通信模塊的能耗。各項參數值設置如表1所示。

表1 能耗分析參數值

仿真實驗分別測定了占空比不同與節點移動速度不同情況下，網絡中任意一個節點完成一次鄰居發現的平均能耗，得到的數據如圖7所示。

圖7 節點平均能耗

由圖7(a)可以發現，SPND算法中節點能實現較小的能耗，且隨著占空比的增加，節點用于鄰居發現的能耗能減少很可觀的一部分，而GBD算法中節點能耗則趨于穩定。由圖 7(b)可以發現，網絡中節點能耗會因為節點的移動速度增大而增大，但是SPND算法總能取得比GBD算法更小的網絡能耗。

5.2.4 限定時延內的節點發現比率

本節將展示在限定時延情況下的節點發現比率，并將SPND算法與經典的Disco算法與Birthday算法進行對比。當網絡中節點占空比為 0.05，節點移動速度為3 m/s時，得到節點限定時延的發現比率如圖8所示。

圖8 限定時延的發現比率

由圖 8可以發現，當限定時延較小時，SPND算法與 Birthday算法一樣，發現比率上升較快，Disco算法上升較慢。而到一定比率后，Birthday算法出現了上升較慢的問題，而 SPND算法能與Disco算法一樣保持較快的上升速度。最終，SPND算法能實現在1 300個時間片左右實現發現比率收斂到1，比Disco算法快大約200個時間片。

5.3 實驗總結

本文通過將SPND算法與其他算法的性能進行比較，分別從網絡平均發現時延、節點蘇醒次數、節點能耗及限定時延內的節點發現比率這4個方面進行對比。仿真實驗數據表明，SPND算法的鄰居發現時延比GBD算法減小了約19%，同時網絡能耗減少了約30%。此外，在限定時延的發現比率方面，SPND發現比率收斂到1的速度比Disco算法快13%。算法性能對比如表2所示。

表2 算法性能對比

其中，Disco、Birthday算法均屬于被動式蘇醒算法，節點不會主動蘇醒。

6 結束語

本文針對移動低占空比無線傳感網中節點主動蘇醒發現鄰居能耗較高的問題，提出了一種新的低能耗的選擇性主動蘇醒快速鄰居發現（SPND）算法。該算法在使用共享鄰居信息方法構建節點初始鄰居集合后，在下一步發現鄰居時，通過劃分節點鄰居子集合，有選擇地進行指定節點主動蘇醒時刻，實現節點低能耗的鄰居發現。理論分析及實驗表明，SPND算法在網絡能耗大幅度優于 Disco、GBD等算法的同時，還能實現發現時延比Disco、GBD等算法更小。

在主動式鄰居發現算法中，節點根據鄰居信息主動蘇醒，要求蘇醒時能與潛在鄰居節點通信，因此，對網絡中節點時鐘同步的要求較高。但是，網絡經過一段時間的工作后，節點的時鐘會發生漂移。因此，下一步將針對節點時鐘會發生漂移的異步網絡進行研究。

參考文獻：

[1]RAZAQUE A,ELLEITHY K M. Low duty cycle,energy-efficient and mobility-based boarder node-MAC hybrid protocol for wireless sensor networks[J]. Journal of Signal Processing Systems,2015,81(2): 265-284.

[2]GUO S,YANG Y,WANG C. DaGCM: a concurrent data uploading framework for mobile data gathering in wireless sensor networks[J].IEEE Transactions on Mobile Computing,2016,15(3): 610-626.

[3]陳權,高宏. 低占空比無線傳感器網絡中基于動態切換的實時路由協議[J]. 通信學報,2015,10(36): 224-234.CHEN Q,GAO H. Dynamic switching based real-time routing in low-duty-cycle wireless sensor networks[J]. Journal on Communications,2015,10(36): 224-234.

[4]QIU Y,LI S,XU X,et al. Talk more listen less: energy-efficient neighbor discovery in wireless sensor networks[C]// IEEE International Conference on Computer Communications. 2016: 1-9.

[5]MENG T,WU F,CHEN G. Code-based neighbor discovery protocols in mobile wireless networks[J]. IEEE Transactions on Networking,2016,24(2): 806-819.

[6]MCGLYNN M J,BORBASH S A. Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks[C]// The ACM MobiHoc. 2001: 137-145.

[7]YOU L,YUAN Z,YANG P,et al. ALOHA-like neighbor discovery in low-duty-cycle wireless sensor networks[C]//2011 IEEE Wireless Communications and Networking Conference (WCNC). 2011: 749-754.

[8]JIANG J R,TSENG Y C,HSU C S,et al. Quorum-based asynchronous power-saving protocols for IEEE 802.11 ad hoc networks[C]//Proceedings of Mobile Networks and Applications. 2005,10(12):169-181.[9]ZHENG R,HOU J C,SHA L. Asynchronous wakeup for ad hoc networks[C]// The 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing. 2003: 35-45.

[10]DUTTA P,CULLER D. Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications[C]//The 6th ACM Conference on Embedded Network Sensor Systems. 2008: 71-84.

[11]NIVEN I,ZUCKERMAN H S. An introduction to the theory of numbers.4th ed[J]. American Mathematical Monthly,1961,68(6): 401-405.

[12]KANDHALU A,LAKSHMANAN K,RAJKUMAR R R. U-connect:a low-latency energy-efficient asynchronous neighbor discovery protocol[C]//The 9th ACM/IEEE International Conference on Information Processing in Sensor Networks. 2010: 350-361.

[13]CHEN H,LOU W,WANG Z,et al. On achieving asynchronous energy-efficient neighbor discovery for mobile sensor networks[J]. IEEE Transactions on Emerging Topics in Computing,2016,PP(99): 1-12.

[14]KINDT P H,YUNGE D,REINERTH G,et al. Griassdi: mutually assisted slotless neighbor discovery[C]//ACM/IEEE International Conference on Information Processing in Sensor Networks. 2017: 93-104.

[15]CHEN L,SHU Y,GU Y,et al. Group-based neighbor discovery in low-duty-cycle mobile sensor networks[J]. IEEE Transactions on Mobile Computing,2016,15(8): 1996-2009.

[16]陳良銀,顏秉姝,張靖宇,等. 移動低占空比傳感網鄰居發現算法[J].軟件學報,2014,25(6): 1352-1368.CHEN L Y,YAN B S,ZHANG J Y,et al. Neighbor discovery algorithm in mobile low-duty-cycle wireless sensor networks[J]. Journal of Software,2014,25(6): 1352-1368.

[17]HUANG T,CHEN H,ZHANG Y,et al. EasiND: effective neighbor discovery algorithms for asynchronous and asymmetric-duty-cycle multi-channel mobile WSNs[J]. Wireless Personal Communications,2015,84(4): 3031-3055.

[18]CAMP T,BOLENG J,DAVIES V. A survey of mobility models for ad hoc network research[J]. Wireless Communications and Mobile Computing,2002,2(5): 483-502.