非對稱異步移動傳感網(wǎng)中低延時鄰居發(fā)現(xiàn)算法

黃庭培，張 亞，李世寶，劉建航

(1.中國石油大學(xué)(華東)計算機科學(xué)與技術(shù)學(xué)院，山東 青島 266580; 2.中國石油大學(xué)(華東)海洋與空間信息學(xué)院，山東 青島 266580)

0 引 言

移動傳感網(wǎng)絡(luò)(Mobile Sensor Network, MSN)[1]功能靈活，易于部署，廣泛應(yīng)用于物聯(lián)網(wǎng)、車載網(wǎng)絡(luò)、移動社交網(wǎng)絡(luò)[2-5]等許多領(lǐng)域。在MSN中，傳感器節(jié)點之間的地理位置和分布常常是不確定的，節(jié)點之間需要經(jīng)過互相發(fā)現(xiàn)才能自組織形成網(wǎng)絡(luò)[6]。因此，鄰居發(fā)現(xiàn)是移動傳感網(wǎng)絡(luò)中必不可少的一部分。

在實際應(yīng)用中，網(wǎng)絡(luò)往往是異步[7]的，不同需求的節(jié)點往往也具有不同的調(diào)度方式。例如，電源供應(yīng)充足的節(jié)點會設(shè)置較大的占空比[8]來迅速地發(fā)現(xiàn)鄰居，這是對稱鄰居發(fā)現(xiàn)協(xié)議[9]無法處理的。非對稱鄰居發(fā)現(xiàn)協(xié)議不要求每個節(jié)點有相同的調(diào)度方式，每個節(jié)點的占空比可以根據(jù)需求調(diào)用。占空比即一周期內(nèi)節(jié)點處于活動狀態(tài)的時間與節(jié)點的總時間之間的比例。

針對此問題，算法Nihao[10]采用多說少聽的原則，信標(biāo)可以在活動、睡眠時隙廣播。然而，該算法中節(jié)點嚴(yán)格遵循預(yù)定義的調(diào)度表來實現(xiàn)鄰居發(fā)現(xiàn)，造成了較大的發(fā)現(xiàn)時延。Q-Connect[11]算法提出信標(biāo)在工作周期的不同時隙內(nèi)進行廣播以保證鄰居發(fā)現(xiàn)的確定性?；谏鲜鏊枷?，本文提出一種名為BMCS的低延時的主動式鄰居發(fā)現(xiàn)算法。

本文的主要工作包括以下3個方面：

1)提出BMCS-A算法，該算法適用于異步對稱場景，其中節(jié)點信標(biāo)與活動時隙分離，信標(biāo)在工作周期的不同時隙內(nèi)進行廣播以保證鄰居發(fā)現(xiàn)的確定性。

2)進一步擴展BMCS-A算法，提出持續(xù)性廣播[12]的BMCS-B算法。該算法適用于節(jié)點具有不同參數(shù)的異步不對稱場景[13]，并且基于鄰居關(guān)系的傳遞性[14]，利用已發(fā)現(xiàn)的鄰居發(fā)現(xiàn)潛在鄰居，加快鄰居發(fā)現(xiàn)的過程。

3)通過仿真實驗評估所提出的BMCS算法，仿真結(jié)果表明，在平均能耗相同的條件下，BMCS算法的最壞發(fā)現(xiàn)時延低于現(xiàn)有的其他鄰居發(fā)現(xiàn)算法。

1 相關(guān)工作

根據(jù)網(wǎng)絡(luò)中節(jié)點的蘇醒方式，將已經(jīng)存在的鄰居發(fā)現(xiàn)算法劃分為主動式鄰居發(fā)現(xiàn)算法[15]和被動式鄰居發(fā)現(xiàn)算法[16]。

1.1 被動式鄰居發(fā)現(xiàn)算法

被動式鄰居發(fā)現(xiàn)算法是指每個節(jié)點按照預(yù)先設(shè)定好的睡眠蘇醒調(diào)度表有規(guī)律地蘇醒，從而進行相互發(fā)現(xiàn)。在基于Quorum[17]系統(tǒng)的鄰居發(fā)現(xiàn)算法中時間被劃分成m2個連續(xù)的時隙，并被組織成一個二維m×m的矩陣。每個節(jié)點隨機選擇任意一行和一列作為自己的活動時隙，并在其他時隙內(nèi)處于休眠狀態(tài)。從而，在m2個連續(xù)的時隙內(nèi)，任意2個節(jié)點間的活動時隙至少能夠重疊2次。為了得到相同發(fā)現(xiàn)時延要求下比算法Quorum更低的占空比，Dutta等人[18]基于中國剩余定理設(shè)計了一種分布式的非對稱鄰居發(fā)現(xiàn)算法，即Disco算法。每個節(jié)點單獨選擇2個素數(shù)p1和p2，使得2個素數(shù)的倒數(shù)之和為節(jié)點的占空比。Disco算法的最大鄰居發(fā)現(xiàn)延時即為2個素數(shù)的乘積。Disco算法的缺點是需要針對不同網(wǎng)絡(luò)場景選擇不同的素數(shù)對，如果節(jié)點選擇了相同的素數(shù)對，則會導(dǎo)致大的發(fā)現(xiàn)延時。

上述幾種發(fā)現(xiàn)算法，節(jié)點均采用被動式鄰居發(fā)現(xiàn)的方式，通過一定的策略來降低2個節(jié)點同時蘇醒的等待時間。這種方式的優(yōu)點是任意2個節(jié)點間不需要信息交互，但也存在任意2個節(jié)點間可能需要等待很長的時間才能完成相互發(fā)現(xiàn)的缺點。

1.2 主動式鄰居發(fā)現(xiàn)算法

Chen等人[11]提出了一種節(jié)點主動蘇醒的鄰居發(fā)現(xiàn)算法Q-Connect。該算法中信標(biāo)在工作周期的不同時隙內(nèi)進行廣播以保證鄰居發(fā)現(xiàn)的確定性。Q-Connect算法，降低了平均發(fā)現(xiàn)時延，但Q-Connect算法只適用于對稱的場景。

Qiu等人[10]基于“多說少聽”的原則提出了一種主動式的鄰居發(fā)現(xiàn)算法Nihao。Nihao通過增加信標(biāo)廣播的數(shù)量來降低發(fā)現(xiàn)時延。節(jié)點在一個周期(m×n)的前m個時隙處于監(jiān)聽狀態(tài)，每隔m個時隙進入廣播狀態(tài)，整個周期內(nèi)發(fā)送n個信標(biāo)消息。在該算法中，節(jié)點在睡眠狀態(tài)主動蘇醒進行發(fā)送信標(biāo)，因此，2個節(jié)點可以在較少的時間內(nèi)完成雙向發(fā)現(xiàn)，減少了發(fā)現(xiàn)時延。Nihao發(fā)送了多個信標(biāo)消息，造成了較高的能耗，并且沒有考慮節(jié)點時鐘偏移等問題。

綜上所述，主動式鄰居發(fā)現(xiàn)算法可以在平均時延和能耗方面取得一個較好的平衡，但是依然存在限定時延下發(fā)現(xiàn)鄰居概率不高等問題。

2 算法設(shè)計

本章中，首先介紹信標(biāo)與活動時隙分離的鄰居發(fā)現(xiàn)模型，其次介紹提出的BMCS-A鄰居發(fā)現(xiàn)算法的基本鄰居發(fā)現(xiàn)過程，之后將BMCS-A算法進行擴展，提出適用于異步非對稱場景的BMCS-B算法，并利用信標(biāo)消息的傳遞性，加快鄰居發(fā)現(xiàn)的過程。

2.1 鄰居發(fā)現(xiàn)模型

在確定型鄰居發(fā)現(xiàn)算法中，時隙模型[19]將連續(xù)的時間片分為相同的間隔，稱為時隙。時隙分為喚醒時隙和睡眠時隙。在喚醒時隙，節(jié)點進入活動狀態(tài)，在時隙的開頭或結(jié)尾廣播信標(biāo)，之后切換成監(jiān)聽狀態(tài)來接收鄰近節(jié)點的信標(biāo)消息。因此，節(jié)點在發(fā)送或者接收信標(biāo)時都處于活動狀態(tài)，這對鄰居發(fā)現(xiàn)來說是不節(jié)能的?；趯⑿艠?biāo)的監(jiān)聽和廣播分配到不同的時隙可能更節(jié)能的想法，將喚醒時隙分為廣播時隙和監(jiān)聽時隙。在信標(biāo)與活動時隙分離的鄰居發(fā)現(xiàn)模型[8]的基礎(chǔ)上，定義如下的鄰居發(fā)現(xiàn)模型：

定義1 廣播時隙：節(jié)點在時隙的開頭或結(jié)尾廣播信標(biāo)，并在時隙的其余部分保持睡眠狀態(tài)。

定義2 監(jiān)聽時隙：在該時隙中，節(jié)點保持在監(jiān)聽狀態(tài)以接收信標(biāo)。

定義3 睡眠時隙：節(jié)點保持睡眠狀態(tài)的時隙。

如圖1所示，時隙0是監(jiān)聽時隙，時隙1～時隙3是廣播時隙，時隙4～時隙7是睡眠時隙，黑色箭頭代表信標(biāo)。為了便于描述，將節(jié)點m的睡眠蘇醒調(diào)度定義為：

(1)

其中θ是發(fā)送信標(biāo)的時間與廣播時隙持續(xù)時間之間的比例，頭信標(biāo)和尾信標(biāo)分別表示信標(biāo)在廣播時隙的開頭或結(jié)尾廣播的信標(biāo)。

Kandhalu等人[20]提出，當(dāng)2個相鄰節(jié)點同時處于活動時隙時，一對相鄰節(jié)點可以實現(xiàn)發(fā)現(xiàn)成功?；谛艠?biāo)的廣播和活動時隙分離的發(fā)現(xiàn)模型，將2個相鄰節(jié)點之間的發(fā)現(xiàn)定義為它們可以從彼此接收信標(biāo)：

(2)

當(dāng)節(jié)點B發(fā)現(xiàn)節(jié)點A時，t1和t2分別表示2個相鄰節(jié)點A和B的本地時隙索引；當(dāng)節(jié)點A發(fā)現(xiàn)節(jié)點B時，t3和t4分別表示2個相鄰節(jié)點A和B的本地時隙索引。公式(2)表示節(jié)點A和節(jié)點B能夠在監(jiān)聽時隙中接收到彼此的信標(biāo)消息，可以實現(xiàn)雙向發(fā)現(xiàn)。

2.2 BMCS-A算法

本文首先考慮異步對稱場景，如果節(jié)點A的第i個時隙的開頭與節(jié)點B的第j個時隙的開頭對齊，i和j不相等，在這種場景下仍然是異步的。保證2個相鄰節(jié)點最終能夠以足夠高的能量效率發(fā)現(xiàn)彼此是一個挑戰(zhàn)。為了解決這一問題，本文提出高效的BMCS-A鄰居發(fā)現(xiàn)算法。

第一階段，節(jié)點A在任意一時刻蘇醒，按照預(yù)先設(shè)定的睡眠蘇醒調(diào)度表有規(guī)律地蘇醒，廣播信標(biāo)探測周圍的鄰居節(jié)點。第二階段，節(jié)點B接收到節(jié)點A的信標(biāo)消息后，通過調(diào)整自身信標(biāo)的發(fā)送時刻，主動蘇醒廣播信標(biāo)，實現(xiàn)雙向發(fā)現(xiàn)。

2.2.1 動態(tài)廣播信標(biāo)

為了更清楚地描述BMCS-A算法，定義周期和子周期，如下所示：

定義4 子周期：2個監(jiān)聽時隙的周期，等于2個連續(xù)監(jiān)聽時隙之間的時隙數(shù)，用字母C表示。

定義5 周期：睡眠蘇醒調(diào)度的總周期，等于一個周期中的時隙數(shù)，用字母T表示。

定義6 距離：當(dāng)前的廣播時隙到下一個監(jiān)聽時隙的間隔，等于這個區(qū)間內(nèi)的時隙數(shù)，用字母d表示，被包含在信標(biāo)消息中。

BMCS-A算法的睡眠蘇醒調(diào)度[21]如下：

2)每個子周期的開始時隙是一個監(jiān)聽時隙。

如圖2所示，在一個周期中有2個子周期，即子周期0和1。其中C=8,r=2,N=2。在子周期0內(nèi)，廣播時隙位于第1個時隙到第2個時隙，在子周期1內(nèi)，廣播時隙位于第3個時隙到第4個時隙內(nèi)。

(3)

在圖2中，時隙0和時隙8是監(jiān)聽時隙，因此Ψ(m,0)=1,Ψ(m,8)=1。時隙1和時隙2為廣播時隙，Ψ(m,1)=Ψ(m,2)=θ+。同樣時隙11和時隙12為子周期1的廣播時隙，Ψ(m,11)=Ψ(m,12)=θ+。

2.2.2 主動廣播信標(biāo)

當(dāng)鄰居節(jié)點接收信標(biāo)后，它可以在某個時隙主動廣播信標(biāo)消息，其索引根據(jù)距離d計算。如圖3所示，當(dāng)節(jié)點B從節(jié)點A接收信標(biāo)后，獲取節(jié)點A從當(dāng)前廣播時隙到下一個監(jiān)聽時隙的距離d。節(jié)點B得知點節(jié)點A將在5個時隙后處于監(jiān)聽狀態(tài)。因此，節(jié)點B將在5個時隙后，即節(jié)點B的本地時隙6的末尾主動地廣播信標(biāo)。節(jié)點A和B的時隙t狀態(tài)的函數(shù)Ψ(A,t1)和Ψ(B,t2)表述為公式(4)和公式(5)。

(4)

(5)

2.3 BMCS-B算法

在實際應(yīng)用中，很難實現(xiàn)不同節(jié)點的占空比相同，因此有必要進一步考慮節(jié)點不對稱的情況。在節(jié)點不對稱的情況下，如果節(jié)點的時隙模式設(shè)計得不好，可能2個相鄰節(jié)點的廣播時隙和監(jiān)聽時隙總是相互錯過，從而導(dǎo)致它們永遠無法發(fā)現(xiàn)對方。為了解決這一問題，基于“多說少聽”的思想，本文提出適用于非對稱異步的BMCS-B鄰居發(fā)現(xiàn)算法。

在Nihao算法中，節(jié)點通過增加信標(biāo)消息的發(fā)送次數(shù)來減少自身蘇醒的次數(shù)，從而達到降低時延的目的；本節(jié)中基于“多說少聽”的原則提出一種持續(xù)性廣播的主動式鄰居發(fā)現(xiàn)算法?！俺掷m(xù)性”是指節(jié)點在第一個子周期內(nèi)持續(xù)性地廣播信標(biāo)，鄰居節(jié)點在接收到信標(biāo)后，獲得發(fā)送節(jié)點下一次的蘇醒時刻，通過調(diào)整自身下一次信標(biāo)的發(fā)送時間，使發(fā)送節(jié)點可以接收到鄰居節(jié)點的信標(biāo)消息，實現(xiàn)雙向發(fā)現(xiàn)成功。

假設(shè)可以預(yù)先獲取所有節(jié)點的占空比，BMCS-B分為2個階段。第一階段，如圖4所示，節(jié)點K的占空比最小，節(jié)點K在某一時刻蘇醒，在自己的第一個子周期(除了監(jiān)聽時隙)的時隙內(nèi)連續(xù)發(fā)送信標(biāo)，探測周圍的鄰居節(jié)點。在網(wǎng)絡(luò)通信較好的場景下，在C(9)個時隙內(nèi)，能夠保證節(jié)點K通信范圍內(nèi)的節(jié)點(如I、J等)都可以接收到它發(fā)送的信標(biāo)消息。信標(biāo)包含節(jié)點K在C個時隙后的第一次蘇醒時刻的消息。第二階段，節(jié)點I在時隙8接收到節(jié)點K的信標(biāo)消息之后，主動在時隙13發(fā)送信標(biāo)，節(jié)點K會在時隙10接收到節(jié)點I的信標(biāo)，從而實現(xiàn)雙向發(fā)現(xiàn)。

節(jié)點I、J和K的時隙t狀態(tài)的函數(shù)如公式(6)與公式(7)所示。Ψ(I,t2)=Ψ(J,t3)和Ψ(K,t1)表示如下：

(6)

(7)

2.4 協(xié)作式BMCS-B算法

基于信標(biāo)消息的傳遞性，為節(jié)點設(shè)計了鄰居發(fā)現(xiàn)列表[22]。節(jié)點K發(fā)現(xiàn)第一個鄰居節(jié)點I時，將節(jié)點I加入到自身的鄰居發(fā)現(xiàn)的列表中，并獲得了節(jié)點I的睡眠蘇醒時刻表。當(dāng)節(jié)點K發(fā)現(xiàn)新的鄰居節(jié)點J時，將節(jié)點J加入到自身的鄰居發(fā)現(xiàn)列表中，并將自身的鄰居發(fā)現(xiàn)列表分享給節(jié)點J。節(jié)點J根據(jù)節(jié)點K的鄰居發(fā)現(xiàn)列表得知節(jié)點I下一次的蘇醒時間，因此，節(jié)點J在該時刻主動地蘇醒廣播信標(biāo)來進行鄰居發(fā)現(xiàn)。

3 性能仿真分析

3.1 仿真環(huán)境

本文使用Matlab[23-24]仿真平臺，在該平臺上實現(xiàn)BMCS算法與其他經(jīng)典算法對比的仿真。為了減少實驗誤差造成的影響，每組實驗進行10000次，數(shù)據(jù)取平均值，比較同一占空比下的最壞發(fā)現(xiàn)時延。σ的值設(shè)置為0.054,r的值由定理1計算給出。其次，本文還對不同節(jié)點具有不同占空比的非對稱場景進行了性能比較。

3.2 性能指標(biāo)

3.2.1 BMCS-A算法的性能指標(biāo)

1)平均能耗。

(8)

2)最壞發(fā)現(xiàn)時延。

3)參數(shù)r。

(9)

為了獲得最小的最壞發(fā)現(xiàn)時延，信標(biāo)數(shù)量r[26]的值，如公式(10)。

(10)

(11)

3.2.2 BMCS-B算法的性能指標(biāo)

占空比時延乘積[21]。

(12)

對于在同一通信范圍內(nèi)的S個節(jié)點來說，平均能耗P平均可以表示為：

文獻[27]提出了將占空比與時延的乘積作為評價鄰居發(fā)現(xiàn)算法性能的指標(biāo)。如果2個指標(biāo)都小，則它們的乘積也小，算法性能更好。本文采用同樣的方式對BMCS-B算法進行評估，占空比和發(fā)現(xiàn)時延乘積為：

(13)

(14)

3.3 實驗結(jié)果

3.3.1 對稱場景

本文將BMCS-A與Disco、Searchlight[28]、U-Connect、Q-ConnectUI在異步對稱場景中進行對比。在圖6(a)中，DC=5%, BMCS-A算法中節(jié)點可以在160個時隙之內(nèi)發(fā)現(xiàn)成功，該算法最壞發(fā)現(xiàn)時延明顯低于其他算法。在圖6(b)中，DC=10%, Q-ConnectUI的最壞發(fā)現(xiàn)時延為70個時隙，而BMCS-A算法僅僅為50個時隙?；谏鲜龇治?，可以聲稱所提出的BMCS-A算法在異步對稱場景中具有較好的性能。

3.3.2 非對稱場景

如圖7(a)所示，占空比分別為1%和5%的節(jié)點的累積發(fā)現(xiàn)時延。BMCS-B可以在1400個時隙之內(nèi)成功發(fā)現(xiàn)彼此，比BMCS-A少了1200個時隙。在圖7(b)中，節(jié)點占空比分別為1%和10%時，BMCS-B的最壞發(fā)現(xiàn)時延為900個時隙，BMCS-A的最壞發(fā)現(xiàn)時延為2100個時隙。BMCS-B算法比Searchlight(3900)、G-Nihao(4200)、Disco(3300)最壞發(fā)現(xiàn)時延分別降低了76.92%、78.57%和72.73%。因此，可以證明BMCS-B算法在平均能耗相同的情況下，最壞發(fā)現(xiàn)時延遠低于其他算法。

此外，本文將協(xié)作式BMCS-B算法與經(jīng)典算法進行了對比分析。如圖8(a)所示，DC=1%和DC=5%協(xié)作式BMCS-B在700個時隙內(nèi)保證2個節(jié)點發(fā)現(xiàn)成功。如圖8(b)所示，協(xié)作式BMCS-B可以在600個時隙內(nèi)保證發(fā)現(xiàn)成功，比Searchlight算法、G-Nihao算法、Disco算法發(fā)現(xiàn)時延分別降低了84.62%、85.71%和81.82%?；谝陨戏治觯梢缘贸鰠f(xié)作式BMCS-B算法在較低的占空比下的性能更高。

4 結(jié)束語

在本文中，基于信標(biāo)與活動時隙分離的模型提出的BMCS-A算法在異步對稱場景中具有更低的最壞發(fā)現(xiàn)時延。此外，針對于異步非對稱場景，提出了一種基于主動喚醒的持續(xù)性廣播的算法BMCS-B，并且利用已發(fā)現(xiàn)的鄰居信息去發(fā)現(xiàn)潛在的鄰居，加快了鄰居發(fā)現(xiàn)的過程。最后，通過仿真實驗驗證了在平均能耗相同的情況下，發(fā)現(xiàn)時延比Searchlight、G-Nihao和Disco等算法更低。