移動低占空比傳感網(wǎng)中時延感知的鄰居發(fā)現(xiàn)算法

李文娟，王寶珠，楊浩瀾

(1.重慶郵電大學移通學院，重慶 401520; 2.重慶郵電大學，重慶 400044)

0 引 言

作為新型自組織網(wǎng)絡一樣，移動低占空比無線傳感網(wǎng)絡(Mobile Low-Duty-Cycle Wireless Sensor Networks, MLDC-WSNs)與傳統(tǒng)的無線傳感網(wǎng)絡(Wireless Sensor Networks, WSNs)[1]既有相同點，也有不同之處。相同點在于：它們都有海量、微型的、存儲容量和計算能力有限的傳感節(jié)點組成[2]。不同之處在于：MLDC-WSNs內(nèi)的節(jié)點不僅可以移動，而且休眠時間長(即低占空比)[3-5]。

MLDC-WSNs使節(jié)點以低占空比狀態(tài)保存節(jié)點能量。然而，低占空比技術(shù)雖然保存了節(jié)點能量，延長了網(wǎng)絡壽命，但是其產(chǎn)生一個新的問題—以低占空比工作的節(jié)點如何發(fā)現(xiàn)鄰居節(jié)點[6]。

在MLDC-WSNs中，傳感節(jié)點多數(shù)時間保持休眠狀態(tài)，這就可能出現(xiàn)原本兩個物理鄰居節(jié)點，卻不能發(fā)現(xiàn)彼此現(xiàn)象，即它們并不知道彼此的存在。若再考慮傳感節(jié)點的移動性，發(fā)現(xiàn)鄰居節(jié)點更難度。

而鄰居發(fā)現(xiàn)是構(gòu)建網(wǎng)絡拓撲的重要操作。網(wǎng)絡內(nèi)的節(jié)點需要快速地發(fā)現(xiàn)鄰居，進而形成網(wǎng)絡。由于網(wǎng)絡內(nèi)所有節(jié)點需要發(fā)現(xiàn)鄰居，一個快速、低能耗的鄰居發(fā)現(xiàn)策略能夠提高網(wǎng)絡性能，延長網(wǎng)絡壽命[7-8]。而在MLDC-WSNs中，節(jié)點采用低占空比模式工作，并要求節(jié)點間同步喚醒。這就使得節(jié)點可能需要等待較長時間，鄰居節(jié)點才喚醒。這增加了時延。

因此，如何以低時延、低功耗方式發(fā)現(xiàn)鄰居成為MLDC-WSNs的研究熱點。目前，現(xiàn)有的多數(shù)研究策略是讓節(jié)點主動喚醒(actively wake up)去發(fā)現(xiàn)鄰居。但是這種策略要求節(jié)點喚醒多次，增加了能量消耗。

為此，提出時延感知的鄰居發(fā)現(xiàn)(Low-latency -Aware Neighbor Discovery, LAND)算法。LAND算法通過預測節(jié)點的移動距離，估計節(jié)點鄰居集，并進行主動喚醒。仿真結(jié)果表明，提出的LAND算法有效地控制發(fā)現(xiàn)鄰居的時延，并提高鄰居發(fā)現(xiàn)率。

1 約束條件及問題描述

1.1 約束條件

令G={V,E}表示MLDC-WSNs網(wǎng)絡，其中V表示n個傳感節(jié)點的節(jié)點集，即V={s1,s2,…,sn}。而E表示節(jié)點是否與其他節(jié)點連通的信息。G內(nèi)節(jié)點采用低占空比工作模式，如圖1所示。節(jié)點在多數(shù)時隙內(nèi)處于休眠，少數(shù)時隙處于喚醒。在喚醒狀態(tài)時，節(jié)點可以發(fā)送數(shù)據(jù)和與其他節(jié)點通信。此外，節(jié)點可以在任何時隙主動喚醒，并發(fā)送數(shù)據(jù)包，但是，只能在預定的喚醒時隙內(nèi)接收數(shù)據(jù)包。

圖1 節(jié)點的低占空模式

令R表示MLDC-WSNs內(nèi)節(jié)點的通信半徑。節(jié)點可以與其通信范圍內(nèi)的節(jié)點通信。此外，引用隨機路點移動 (Random Waypoint Mobile, RWM)模型[9]。在RWM模型中，節(jié)點隨機地選擇移動方向，且在速度范圍[0,?max]內(nèi)移動。在特定時間Δt內(nèi)，節(jié)點可以移動的最大距離為Δt×?max。

1.2 問題描述

假定節(jié)點si和節(jié)點sj在時間t可以相遇。節(jié)點在Δt內(nèi)，它們在彼此通信范圍內(nèi)。它們均在Δt喚醒，且Δt不小于節(jié)點實施鄰居發(fā)現(xiàn)的最小時間tmin(Δt≥tmin)。

基于上述假設，節(jié)點si和節(jié)點sj能夠在[t,t+Δt]內(nèi)發(fā)現(xiàn)鄰居。令δ表示發(fā)現(xiàn)鄰居的時延，其定義如式(1)所示：

δ=t+Δt-t0

(1)

其中t0表示兩個節(jié)點能夠相互通信的時刻。而t+Δt表示這兩個節(jié)點完成相互發(fā)現(xiàn)的時刻。

令Pij表示節(jié)點si和節(jié)點sj在彼此通信范圍內(nèi)能夠發(fā)現(xiàn)彼此的概率。若Pij(t)=0，則表示它們在t時間不能夠發(fā)現(xiàn)彼此；若Pij(t)=1，則表示它們能夠發(fā)現(xiàn)彼此。

令P(t)表示鄰居發(fā)現(xiàn)率，且P(t)=m/N。其中m表示發(fā)現(xiàn)的鄰居數(shù)，而N表示總的鄰居數(shù)。因此，MLDC-WSNs中鄰居發(fā)現(xiàn)問題可簡述為：以最低的時延實現(xiàn)最大化的鄰居發(fā)現(xiàn)率：

{minδ,maxP(t)}

(2)

2 LAND算法

LAND算法由有兩個階段構(gòu)成。在第一階段，節(jié)點依據(jù)網(wǎng)絡部署，構(gòu)建初始節(jié)點集；在第二階段，節(jié)點有選擇性地主動喚醒節(jié)點，并發(fā)現(xiàn)鄰居。

2.1 第一階段

第一步：網(wǎng)絡內(nèi)每個節(jié)點在自己喚醒時隙內(nèi)廣播消息，通知網(wǎng)絡，自己的存在。如圖2所示，在時隙t0，節(jié)點si和節(jié)點sj在彼此通信范圍內(nèi)，能夠接收彼此廣播的消息。然后，它們交換休眠-喚醒時刻表(Sleep wake-up Timetable, SWT)信息。

圖2 初始鄰居節(jié)點的構(gòu)建

一旦收到節(jié)點si的鄰居信息，節(jié)點sj就在節(jié)點si的鄰居節(jié)點(為節(jié)點sk)的喚醒時刻t3主動喚醒，并向節(jié)點sk發(fā)送確認信息ACK：節(jié)點sk是否能成為自己的鄰居節(jié)點。如果節(jié)點sk收到ACK，則節(jié)點sk成為節(jié)點sj的鄰居節(jié)點。即節(jié)點sj發(fā)現(xiàn)了新的鄰居節(jié)點sk。

2.2 第二階段

一旦構(gòu)建了初始鄰居集后，就進行第二階段。第二階段主要考慮節(jié)點的移動問題。即當有節(jié)點在節(jié)點si周圍移動，節(jié)點si就主動喚醒，進而發(fā)現(xiàn)鄰居節(jié)點。

圖3 節(jié)點移動

dix∈[0,R-ΔS)

(3)

dix∈[R+ΔS,+∞)

(4)

dix∈[R-ΔS,R-ΔS)

(5)

圖4 節(jié)點鄰居集

(6)

3 性能分析

3.1 仿真參數(shù)

利用MATLAB軟件建立仿真平臺。在1000 m×1000 m區(qū)域內(nèi)隨機部署500個低占空比節(jié)點。所有節(jié)點依據(jù)RWM模型在區(qū)域內(nèi)移動。節(jié)點默認的移動速度為1 m/s，最大移動速度?max=1.3 m/s。節(jié)點占空比為5%，這意味著每20個時隙只有一個時隙，節(jié)點保持喚醒狀態(tài)?？紤]T=5000個時隙節(jié)點，每個時隙時長為10 ms。節(jié)點默認的通信半徑R=100 m。

此外，為了更好地分析LAND性能，選擇文獻[10]的Disco、文獻[11]的CBD和文獻[12]的Birthday作為參照，并分析它們的平均鄰居發(fā)現(xiàn)時延、喚醒次數(shù)和節(jié)點鄰居發(fā)現(xiàn)率。

3.2 發(fā)現(xiàn)鄰居的平均時延

本次實驗分析占空比和移動速度對平均時延的影響，如圖5所示。

圖5 發(fā)現(xiàn)鄰居的平均時延

圖5(a)顯示了占空比對平均時延的影響，其中節(jié)點移動速度為1 m/s，占空比從1%～10%變化。從圖可知，占空比的增加，降低了平均時延。相比于CBD和Disco算法相比，LAND算法的平均時延得到有效控制。例如，當占空比為0.05時，LAND算法的時延為10s, 而Disco和CBD算法的時延分別62 s和22 s。

圖5(b)顯示了移動速度對平均時延的影響，其中占空比為3%，節(jié)點移動速度從1m/s至10m/s變化。從圖可知，平均時延隨移動速度的加快而下降。原因在于：移動速度的加快，節(jié)點相遇的頻率增加，這有利于發(fā)現(xiàn)鄰居節(jié)點。相比于Disco和CBD算法，LAND算法的平均時延隨移動速度變化波動小，且保持低的平均時延。

3.3 喚醒次數(shù)

本次實驗分析節(jié)點在發(fā)現(xiàn)所有鄰居節(jié)點所需的次數(shù)。圖6顯示Disco、CBD和LAND算法的喚醒次數(shù)隨低占比的變化。

圖6 喚醒次數(shù)隨低占比的變化

從圖6可知，喚醒次數(shù)隨占空比的增加呈下降趨勢。原因在于：占空比越高，節(jié)點喚醒的時隙數(shù)越高，就無需多數(shù)喚醒節(jié)點。此外，相比Disco和CBD算法，LAND算法有效地控制喚醒次數(shù)。例如，當占空比為0.07時，LAND算法的喚醒次數(shù)約為12，而Disco和CBD算法的喚醒次數(shù)達到約26和22，而Birthday算法的喚醒次數(shù)為約15。

3.4 節(jié)點鄰居發(fā)現(xiàn)率

本次實驗分析發(fā)現(xiàn)時延對鄰居發(fā)現(xiàn)率的影響，其中低占比為0.05，移動速度為3 m/s。

從圖7可知，當發(fā)現(xiàn)時延較低時，LAND算法和Birthday算法的發(fā)現(xiàn)率相近，它們能夠快速地發(fā)現(xiàn)鄰居。相比之下，Disco算法發(fā)現(xiàn)鄰居節(jié)點速度較慢。當發(fā)現(xiàn)率增長一定量后，Birthday算法的發(fā)現(xiàn)率的增長速度放緩，而LAND算法的發(fā)現(xiàn)率仍能夠維持快速地增長。此外，當發(fā)現(xiàn)時延為1300個時隙時，LAND算法的鄰居發(fā)現(xiàn)率接近于1，比Disco算法提高了近200個時隙。

圖7 節(jié)點鄰居發(fā)現(xiàn)率

4 結(jié) 語

針對MLDC-WSNs的發(fā)現(xiàn)鄰居節(jié)點問題，提出時延感知的鄰居發(fā)現(xiàn)LAND算法。LAND算法通過共享鄰居節(jié)點信息，先構(gòu)建初始鄰居集，然后，再有選擇地喚醒節(jié)點，并將鄰居集劃分為兩個子集。再依據(jù)節(jié)點移動距離估計因節(jié)點移動而新構(gòu)建的節(jié)點集。仿真結(jié)果表明，相比于Disco和GDB算法，LAND算法降低了發(fā)現(xiàn)鄰居節(jié)點的時延，并提高鄰居發(fā)現(xiàn)率。