移動低占空比無線傳感網(wǎng)中低能耗的主動鄰居發(fā)現(xiàn)算法

梁俊斌，周翔，李陶深

（廣西大學(xué)計算機與電子信息學(xué)院廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室，廣西 南寧 530004）

1 引言

移動低占空比無線傳感網(wǎng)（MLDC-WSN,mobile low-duty-cycle wireless sensor network）是近年出現(xiàn)的一種新型自組織網(wǎng)絡(luò)。它與傳統(tǒng)的無線傳感器網(wǎng)絡(luò)（WSN,wireless sensor network）一樣，由大量能量、通信范圍、存儲容量和計算能力均有限的節(jié)點組成，主要部署在人類無法進入的惡劣環(huán)境中，從事長期的監(jiān)測或跟蹤任務(wù)[1,2]。但是，它與WSN有明顯的區(qū)別：WSN中節(jié)點是靜止且保持蘇醒的，而MLDC-WSN中的節(jié)點會長時間進入睡眠狀態(tài)以保存能量，僅在少量時刻蘇醒并通過移動來執(zhí)行任務(wù)[3]。因此，MLDC-WSN的拓?fù)渥兓瘯宇l繁，導(dǎo)致節(jié)點鄰居也不時地發(fā)生改變。

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

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

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

2 相關(guān)工作

根據(jù)喚醒調(diào)度模式的確定性，鄰居發(fā)現(xiàn)算法可以分為概率性鄰居發(fā)現(xiàn)和確定性鄰居發(fā)現(xiàn)。在確定性鄰居發(fā)現(xiàn)算法中，根據(jù)節(jié)點是否主動蘇醒發(fā)現(xiàn)鄰居，又可以進一步劃分為主動式鄰居發(fā)現(xiàn)和被動式鄰居發(fā)現(xiàn)。

2.1 概率性鄰居發(fā)現(xiàn)

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

2.2 確定性鄰居發(fā)現(xiàn)

確定性鄰居發(fā)現(xiàn)中，節(jié)點采用固定的喚醒調(diào)度模式，即節(jié)點處于睡眠或蘇醒狀態(tài)按照預(yù)定的睡眠蘇醒調(diào)度表周期性地重復(fù)。

2.2.1 被動式鄰居發(fā)現(xiàn)

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

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

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

2.2.2 主動式鄰居發(fā)現(xiàn)

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

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

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

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

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

2) 節(jié)點基于概率的選擇性轉(zhuǎn)發(fā)會降低節(jié)點發(fā)現(xiàn)鄰居的可靠性。

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

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

本節(jié)將給出MLDC-WSN的網(wǎng)絡(luò)模型及本文研究問題的描述，同時對相關(guān)術(shù)語進行定義。

3.1 相關(guān)定義

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

定義2 節(jié)點的發(fā)現(xiàn)概率[17]。距離在通信范圍內(nèi)的2個節(jié)點能相互發(fā)現(xiàn)的概率。

定義3 節(jié)點的發(fā)現(xiàn)比率[17]。網(wǎng)絡(luò)的任意節(jié)點發(fā)現(xiàn)的鄰居節(jié)點數(shù)目占所有通信范圍內(nèi)節(jié)點數(shù)目的比率。

定義4 發(fā)現(xiàn)時延[17]。從節(jié)點移動到通信范圍內(nèi)的時刻開始到它們相互發(fā)現(xiàn)時的時間間隔。

3.2 網(wǎng)絡(luò)模型

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

圖1 占空比示意

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

3.3 問題描述

網(wǎng)絡(luò)中的節(jié)點i與節(jié)點j能在某個時刻t實現(xiàn)相互發(fā)現(xiàn)需要滿足2個條件。

1) 在某個時間段Δt內(nèi)，節(jié)點i與節(jié)點j在通信范圍內(nèi)，假設(shè)網(wǎng)絡(luò)中節(jié)點的通信半徑一致為R。

2) 節(jié)點i與節(jié)點j在Δt內(nèi)同時處于蘇醒狀態(tài)，且Δt不小于節(jié)點實現(xiàn)鄰居發(fā)現(xiàn)所需的最小時間。

節(jié)點間同時滿足以上2個條件，才能被稱為節(jié)點i與節(jié)點j能在[t,t+Δt]實現(xiàn)相互發(fā)現(xiàn)。

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

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

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

4 算法設(shè)計

本節(jié)將給出 SPND算法的基本思想及詳細(xì)設(shè)計，并從理論上將SPND算法和已有的鄰居發(fā)現(xiàn)算法進行對比?？紤]到已有的典型算法采用了節(jié)點的主動蘇醒來減小鄰居發(fā)現(xiàn)時延，SPND算法專注于結(jié)合網(wǎng)絡(luò)移動性模型，減少節(jié)點主動蘇醒次數(shù)，從而實現(xiàn)低能耗的主動式鄰居發(fā)現(xiàn)。

4.1 算法基本思想

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

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

SPND算法分為2個階段。網(wǎng)絡(luò)剛部署，構(gòu)建節(jié)點初始鄰居集合為第一階段。選擇性地指定節(jié)點的主動蘇醒時刻，節(jié)點主動蘇醒發(fā)現(xiàn)該時刻的鄰居集合為第二階段。網(wǎng)絡(luò)中的節(jié)點分布式地完成第一階段的鄰居發(fā)現(xiàn)過程，然后節(jié)點間完全異步地從第一階段切換到第二階段。

4.2.1 構(gòu)建初始鄰居集合

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

圖2 構(gòu)建初始鄰居集合

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

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

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

具體算法如算法1所示。

算法1 構(gòu)建初始鄰居集合

1) for (網(wǎng)絡(luò)中每一個節(jié)點i) {

2) while (t＜T) {

3) if (節(jié)點i蘇醒發(fā)現(xiàn)節(jié)點h) {

4) 節(jié)點i和節(jié)點h共享G;

5) } else {節(jié)點i睡眠}

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

7) 節(jié)點i主動蘇醒;

8) 節(jié)點i與節(jié)點k確認(rèn);

9) } } }

每當(dāng)節(jié)點i的鄰居集合Gi加入新的鄰居節(jié)點，循環(huán)執(zhí)行與新加入節(jié)點的鄰居進行確認(rèn)的步驟，即算法 1中的步驟 6)～步驟 8)，直到收到的所有鄰居信息都被確認(rèn)完畢，完成第一階段的初始鄰居集合構(gòu)建。

4.2.2 選擇性指定蘇醒時刻

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

圖3 節(jié)點移動示意

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

圖4 集合劃分示意

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

算法2 集合劃分與確認(rèn)鄰居節(jié)點

1) for (網(wǎng)絡(luò)中每一個節(jié)點i) {

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

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

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

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

8) }}

11) }

13) 節(jié)點i主動蘇醒與節(jié)點l確認(rèn);

14)} } }

4.3 理論分析

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

4.3.1 發(fā)現(xiàn)時延分析

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

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

則節(jié)點j采用Disco算法在t時間內(nèi)發(fā)現(xiàn)所有n-1鄰居節(jié)點的概率可以表示為。它的密度函數(shù)可以表示為

通過概率密度函數(shù)計算節(jié)點j發(fā)現(xiàn)所有鄰居節(jié)點的期望時間為

當(dāng)采用SPND算法構(gòu)建節(jié)點初始鄰居集合時，節(jié)點i被動蘇醒，在時間t內(nèi)發(fā)現(xiàn)通信范圍內(nèi)第一個鄰居節(jié)點j的概率(t)可以表示為

它的概率密度函數(shù)為

通過概率密度函數(shù)計算節(jié)點i發(fā)現(xiàn)所有鄰居節(jié)點的期望時間為

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

4.3.2 蘇醒及主動蘇醒次數(shù)分析

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

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

節(jié)點i可以減少約φ次的主動蘇醒次數(shù)，φ表示為

其中，ΔS是網(wǎng)絡(luò)中節(jié)點一次移動的最大距離，可見在ΔS不為0的情況下，節(jié)點i能減少的蘇醒次數(shù)是很可觀的一部分。

4.3.3 能耗分析

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

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

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

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

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

4.3.4 發(fā)現(xiàn)概率分析

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

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

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

5 實驗及分析

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

5.1 實驗環(huán)境

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

5.2 性能表現(xiàn)

本文分別測定了網(wǎng)絡(luò)平均發(fā)現(xiàn)時延、節(jié)點蘇醒次數(shù)、節(jié)點能耗及限定時延內(nèi)的節(jié)點發(fā)現(xiàn)比率這 4個方面的數(shù)據(jù)，通過這4組仿真實驗數(shù)據(jù)進行SPND算法與其他算法的對比分析。

5.2.1 網(wǎng)絡(luò)平均發(fā)現(xiàn)時延

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

圖5 網(wǎng)絡(luò)平均發(fā)現(xiàn)時延

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

5.2.2 節(jié)點蘇醒次數(shù)

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

圖6 節(jié)點蘇醒次數(shù)

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

5.2.3 節(jié)點能耗

本節(jié)將展示SPND算法的網(wǎng)絡(luò)能耗，并與現(xiàn)有的主動式鄰居發(fā)現(xiàn)算法 GBD進行對比。在此處的網(wǎng)絡(luò)能耗中，仿真實驗考慮了與節(jié)點鄰居發(fā)現(xiàn)相關(guān)的處理器模塊的能耗和通信模塊的能耗。各項參數(shù)值設(shè)置如表1所示。

表1 能耗分析參數(shù)值

仿真實驗分別測定了占空比不同與節(jié)點移動速度不同情況下，網(wǎng)絡(luò)中任意一個節(jié)點完成一次鄰居發(fā)現(xiàn)的平均能耗，得到的數(shù)據(jù)如圖7所示。

圖7 節(jié)點平均能耗

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

5.2.4 限定時延內(nèi)的節(jié)點發(fā)現(xiàn)比率

本節(jié)將展示在限定時延情況下的節(jié)點發(fā)現(xiàn)比率，并將SPND算法與經(jīng)典的Disco算法與Birthday算法進行對比。當(dāng)網(wǎng)絡(luò)中節(jié)點占空比為 0.05，節(jié)點移動速度為3 m/s時，得到節(jié)點限定時延的發(fā)現(xiàn)比率如圖8所示。

圖8 限定時延的發(fā)現(xiàn)比率

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

5.3 實驗總結(jié)

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

表2 算法性能對比

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

6 結(jié)束語

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

在主動式鄰居發(fā)現(xiàn)算法中，節(jié)點根據(jù)鄰居信息主動蘇醒，要求蘇醒時能與潛在鄰居節(jié)點通信，因此，對網(wǎng)絡(luò)中節(jié)點時鐘同步的要求較高。但是，網(wǎng)絡(luò)經(jīng)過一段時間的工作后，節(jié)點的時鐘會發(fā)生漂移。因此，下一步將針對節(jié)點時鐘會發(fā)生漂移的異步網(wǎng)絡(luò)進行研究。

參考文獻：

[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]陳權(quán),高宏. 低占空比無線傳感器網(wǎng)絡(luò)中基于動態(tài)切換的實時路由協(xié)議[J]. 通信學(xué)報,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]陳良銀,顏秉姝,張靖宇,等. 移動低占空比傳感網(wǎng)鄰居發(fā)現(xiàn)算法[J].軟件學(xué)報,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.