劉元梓

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065)

無(wú)線傳感器網(wǎng)絡(luò)低延遲鄰居發(fā)現(xiàn)算法研究

劉元梓

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065)

鄰居發(fā)現(xiàn)問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)（WSNs）通信協(xié)議的重要組成部分之一。由于不需要同步通訊，異步的鄰居發(fā)現(xiàn)算法近年得到較多的關(guān)注。針對(duì)異步網(wǎng)絡(luò)環(huán)境，設(shè)計(jì)一種新穎的鄰居發(fā)現(xiàn)算法，并驗(yàn)證在不同節(jié)點(diǎn)密度、節(jié)點(diǎn)占空比、節(jié)點(diǎn)通信不規(guī)則度以及節(jié)點(diǎn)移動(dòng)方式等情況下，該算法的發(fā)現(xiàn)延遲和能耗。結(jié)果表明，該算法在降低發(fā)現(xiàn)延遲方面取得良好效果，提升網(wǎng)絡(luò)的性能，對(duì)實(shí)時(shí)性要求較高的無(wú)線傳感器網(wǎng)絡(luò)有很高的實(shí)用價(jià)值。

鄰居發(fā)現(xiàn)；動(dòng)態(tài)占空比；發(fā)現(xiàn)延遲

0 引言

鄰居發(fā)現(xiàn)同時(shí)間同步、節(jié)點(diǎn)定位等一樣，是無(wú)線傳感器網(wǎng)絡(luò)的基礎(chǔ)支撐技術(shù)。鄰居發(fā)現(xiàn)對(duì)于節(jié)點(diǎn)識(shí)別周邊環(huán)境的鄰居節(jié)點(diǎn)以及構(gòu)建路由并協(xié)同工作，具有重要意義。無(wú)線傳感器網(wǎng)絡(luò)經(jīng)過(guò)多年的研究發(fā)展，鄰居發(fā)現(xiàn)已不再是一項(xiàng)新的技術(shù)，具有一定量的可參考文獻(xiàn)資料。一直處于喚醒狀態(tài)的節(jié)點(diǎn)發(fā)現(xiàn)的研究主要集中在定向天線，而基于占空比的節(jié)點(diǎn)發(fā)現(xiàn)算法則是多種多樣的。當(dāng)傳感器節(jié)點(diǎn)處于移動(dòng)的環(huán)境中，這種環(huán)境對(duì)發(fā)現(xiàn)時(shí)間有很高要求，即要以盡可能快地速度發(fā)現(xiàn)節(jié)點(diǎn)。

比較著名的傳感器節(jié)點(diǎn)發(fā)現(xiàn)算法有Stochasticbased Protocols[1-2]，Quorum-based Protocols[3]，Disco[4]，UConnect[5]，多信道[6]以及基于沖突的節(jié)點(diǎn)發(fā)現(xiàn)等。這些算法主要集中在怎樣通過(guò)某一類型的調(diào)度算法來(lái)保證一對(duì)節(jié)點(diǎn)可以同時(shí)喚醒，經(jīng)過(guò)驗(yàn)證這些算法是有效的，可以保證節(jié)點(diǎn)在有限的時(shí)間界限內(nèi)發(fā)現(xiàn)其鄰居節(jié)點(diǎn)。Stochastic-based Protocols中，節(jié)點(diǎn)以隨機(jī)循環(huán)的方式監(jiān)聽(tīng)、傳輸或者休眠，在耗能和發(fā)現(xiàn)延遲上進(jìn)行權(quán)衡折中。Quorum-based Protocols闡明在有界限的時(shí)間上保證成對(duì)節(jié)點(diǎn)的喚醒時(shí)間重疊的局限性。Disco介紹了一個(gè)基于中國(guó)剩余定理（Chinese Reminder Theorem）的鄰居發(fā)現(xiàn)算法，算法中節(jié)點(diǎn)選擇一對(duì)素?cái)?shù)作為周期，素?cái)?shù)的選擇要滿足其占空比要求。U-Connect提出了針對(duì)對(duì)稱或者非對(duì)稱的占空比設(shè)置的統(tǒng)一鄰居發(fā)現(xiàn)算法。值得注意的是U-Connect對(duì)于對(duì)稱異步的發(fā)現(xiàn)方案是1.5倍近似算法，而Quorum和Disco則是2倍近似算法。

在傳統(tǒng)的成對(duì)發(fā)現(xiàn)算法中，每個(gè)節(jié)點(diǎn)周期性地處于喚醒狀態(tài)和休眠狀態(tài)，而且傳感器網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)必須是處于彼此的通信范圍之內(nèi)的，只有這樣節(jié)點(diǎn)之間才可以正常通信，進(jìn)而實(shí)現(xiàn)數(shù)據(jù)的傳輸。當(dāng)兩個(gè)節(jié)點(diǎn)分別根據(jù)自己的工作安排進(jìn)行調(diào)度并同時(shí)處于喚醒狀態(tài)時(shí)，兩個(gè)節(jié)點(diǎn)此發(fā)現(xiàn)對(duì)方，并將對(duì)方加入到自己的鄰居表中，至此完成了一個(gè)鄰居節(jié)點(diǎn)的發(fā)現(xiàn)。組發(fā)現(xiàn)算法，同成對(duì)發(fā)現(xiàn)算法一樣，節(jié)點(diǎn)是在喚醒狀態(tài)和休眠狀態(tài)之間周期性地切換。傳感器網(wǎng)絡(luò)節(jié)點(diǎn)處于蘇醒狀態(tài)時(shí)，根據(jù)自己的工作安排調(diào)度進(jìn)行廣播；當(dāng)傳感器網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)同時(shí)處于喚醒狀態(tài)并在彼此的通信范圍內(nèi)時(shí)，一個(gè)節(jié)點(diǎn)發(fā)現(xiàn)了另外一個(gè)節(jié)點(diǎn)，這兩個(gè)節(jié)點(diǎn)便形成一個(gè)組。當(dāng)?shù)谌齻€(gè)節(jié)點(diǎn)與第一個(gè)節(jié)點(diǎn)同時(shí)喚醒時(shí)，第三個(gè)節(jié)點(diǎn)發(fā)現(xiàn)第一個(gè)節(jié)點(diǎn)并將其加入到自己的鄰居表中，同時(shí)第一個(gè)節(jié)點(diǎn)將其發(fā)現(xiàn)的鄰居節(jié)點(diǎn)信息廣播給第三個(gè)節(jié)點(diǎn)；當(dāng)?shù)谌齻€(gè)節(jié)點(diǎn)和第二個(gè)節(jié)點(diǎn)的喚醒時(shí)間同步時(shí)，由于第三個(gè)節(jié)點(diǎn)通過(guò)第一個(gè)節(jié)點(diǎn)已經(jīng)獲知第二個(gè)節(jié)點(diǎn)的信息，此時(shí)只需判斷這個(gè)節(jié)點(diǎn)是否是其鄰居節(jié)點(diǎn)，如果是的話，將其加入到自己的鄰居表中，形成一個(gè)更大的組。以此類推，這個(gè)由鄰居節(jié)點(diǎn)組成的組不斷地?cái)U(kuò)大，從而完成鄰居節(jié)點(diǎn)的發(fā)現(xiàn)。

本文的主要貢獻(xiàn)如下所示：

（1）根據(jù)影響無(wú)線傳感器網(wǎng)絡(luò)能量消耗和延遲的因素，分析現(xiàn)有的鄰居發(fā)現(xiàn)算法的優(yōu)缺點(diǎn)，研究性能更優(yōu)、延遲更低的鄰居發(fā)現(xiàn)算法；

（2）分析已有鄰居發(fā)現(xiàn)算法中節(jié)點(diǎn)的調(diào)度機(jī)制，采取更先進(jìn)的發(fā)現(xiàn)調(diào)度策略。鄰居發(fā)現(xiàn)策略采用群組發(fā)現(xiàn)的思想，所有節(jié)點(diǎn)采用周期性的睡眠調(diào)度機(jī)制，發(fā)現(xiàn)節(jié)點(diǎn)將已發(fā)現(xiàn)的鄰居節(jié)點(diǎn)納入其所在的群組，通過(guò)已有鄰居節(jié)點(diǎn)的鄰居信息來(lái)獲取潛在的鄰居節(jié)點(diǎn)的信息，采用Demand-wakeup機(jī)制主動(dòng)蘇醒以更快的速度發(fā)現(xiàn)更多的鄰居節(jié)點(diǎn)；

（3）研究群組發(fā)現(xiàn)過(guò)程中節(jié)點(diǎn)間信息的推薦機(jī)制，鄰居節(jié)點(diǎn)如何有效地向發(fā)現(xiàn)節(jié)點(diǎn)推薦潛在的鄰居信息來(lái)保證發(fā)現(xiàn)效率的同時(shí)降低能耗以及發(fā)現(xiàn)節(jié)點(diǎn)如何高效選擇鄰居節(jié)點(diǎn)的信息避免過(guò)多接收無(wú)用的信息而造成不必要的能耗；

（4）利用傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)模型預(yù)測(cè)節(jié)點(diǎn)通信范圍內(nèi)潛在的鄰居節(jié)點(diǎn)，根據(jù)潛在的鄰居節(jié)點(diǎn)的數(shù)量動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的占空比，以此更快更多地發(fā)現(xiàn)鄰居節(jié)點(diǎn)；

本文剩余部分的內(nèi)容主要是算法的設(shè)計(jì)與實(shí)現(xiàn)。

1 Disco算法分析

路由器、交換機(jī)等硬件設(shè)備，那么無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)如何通信呢？毫無(wú)疑問(wèn)，所有的工作都是由傳感器節(jié)點(diǎn)自身來(lái)完成。

許多應(yīng)用設(shè)備，包括那些布置在廣闊野外區(qū)域的具有多樣性配置的設(shè)備，例如在野外部署的低廉傳感器，主要用于環(huán)境監(jiān)測(cè)、野生動(dòng)物監(jiān)測(cè)、戰(zhàn)場(chǎng)環(huán)境監(jiān)視以及采集野外環(huán)境信息等。如何精確保證這些傳感器節(jié)點(diǎn)的全局時(shí)間同步是個(gè)具有挑戰(zhàn)性的問(wèn)題，為了解決這個(gè)問(wèn)題，通常采用基于分布式協(xié)調(diào)占空比模式來(lái)決定各自的工作調(diào)度，即由節(jié)點(diǎn)自己的工作調(diào)度決定何時(shí)工作、何時(shí)發(fā)送數(shù)據(jù)、何時(shí)接收數(shù)據(jù)以及何時(shí)進(jìn)入低功耗的休眠狀態(tài)。

為了安排節(jié)點(diǎn)的工作調(diào)度，我們將傳感器設(shè)備（如節(jié)點(diǎn)S）的工作時(shí)間劃分為連續(xù)的固定長(zhǎng)度的時(shí)隙（Time Slots），依據(jù)預(yù)先安裝的協(xié)議，節(jié)點(diǎn)S激活無(wú)線電設(shè)備并將其狀態(tài)在某一段時(shí)隙內(nèi)切換至發(fā)現(xiàn)模式，然后節(jié)點(diǎn)S向網(wǎng)絡(luò)中的并且處于其通信范圍內(nèi)的其他節(jié)點(diǎn)廣播消息，以此來(lái)通知它的存在性，同時(shí)節(jié)點(diǎn)S也偵聽(tīng)其他節(jié)點(diǎn)的信息。如果在某一時(shí)隙，節(jié)點(diǎn)S和其他的節(jié)點(diǎn)同時(shí)處于工作狀態(tài)，即工作調(diào)度出現(xiàn)重疊部分，如果節(jié)點(diǎn)在彼此的通信范圍內(nèi)，它們就能夠互相發(fā)現(xiàn)并成為彼此的鄰居節(jié)點(diǎn)。

定義1：我們通常將上述在時(shí)間方面的調(diào)度機(jī)制成為時(shí)隙參考機(jī)制（Time Slots Reference Mechanism）。

時(shí)隙參考機(jī)制的示意圖如圖1所示。

圖1 時(shí)隙參考機(jī)制示意圖

無(wú)線傳感器網(wǎng)絡(luò)中所有節(jié)點(diǎn)在網(wǎng)絡(luò)中地位是同等的，任何一個(gè)節(jié)點(diǎn)既是發(fā)送節(jié)點(diǎn)也是接收節(jié)點(diǎn)，將自己采集和接收的數(shù)據(jù)信息傳送給離接收者更近的節(jié)點(diǎn)以及向網(wǎng)絡(luò)中的其他節(jié)點(diǎn)廣播從而將其存在性通知給其他節(jié)點(diǎn)；同時(shí)，接收來(lái)自于其他節(jié)點(diǎn)發(fā)送的數(shù)據(jù)信息。無(wú)線傳感器網(wǎng)絡(luò)沒(méi)有固定的用于發(fā)送和接收信息的基礎(chǔ)設(shè)施，不具有手持設(shè)備（如手機(jī)等）固定的用于轉(zhuǎn)接信號(hào)的信號(hào)接收塔和發(fā)送塔，也不具有Internet的專用

在圖1中，我們將節(jié)點(diǎn)的工作周期劃分為蘇醒狀態(tài)（Active State）和休眠狀態(tài)（Dormant State），圖中，我們用黑色區(qū)域時(shí)隙代表蘇醒狀態(tài)，白色區(qū)域時(shí)隙代表休眠狀態(tài)，如果有兩個(gè)或多個(gè)節(jié)點(diǎn)同時(shí)處于蘇醒狀態(tài)（或者說(shuō)工作調(diào)度出現(xiàn)重疊），而且彼此之間可以互相通信，它們之間就可以完成鄰居發(fā)現(xiàn)，成為彼此的鄰居節(jié)點(diǎn)。

Dutta和Culler在文獻(xiàn)[4]中提出異步鄰居發(fā)現(xiàn)算法Disco，該算法基于中國(guó)剩余定理相關(guān)理論，算法中兩個(gè)節(jié)點(diǎn)選擇一對(duì)素?cái)?shù)，使得這兩個(gè)素?cái)?shù)的倒數(shù)分別與節(jié)點(diǎn)期望的占空比相等，采取素?cái)?shù)的好處是可以保證兩個(gè)節(jié)點(diǎn)在工作過(guò)程中會(huì)出現(xiàn)相同的喚醒時(shí)隙，使得節(jié)點(diǎn)間可以相互通信并完成鄰居發(fā)現(xiàn)。在Disco算法中，所有的節(jié)點(diǎn)采取周期性偵聽(tīng)-睡眠機(jī)制，周期性地在蘇醒狀態(tài)（Active State）和休眠狀態(tài)（Dormant State）或者睡眠狀態(tài)（Sleep State）間切換。鄰居發(fā)現(xiàn)的過(guò)程如下：網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)處于另一個(gè)節(jié)點(diǎn)的通信范圍內(nèi)，并且在某一時(shí)刻這兩個(gè)節(jié)點(diǎn)同時(shí)處于蘇醒狀態(tài)，如果一個(gè)節(jié)點(diǎn)的無(wú)線電廣播信息時(shí)，由于另一個(gè)節(jié)點(diǎn)處于蘇醒狀態(tài)可以接收到廣播信息，此時(shí)，兩個(gè)節(jié)點(diǎn)交換數(shù)據(jù)信息，完成鄰居發(fā)現(xiàn)，成為彼此的鄰居節(jié)點(diǎn)。Disco算法的原理如圖2所示。將其加入自己的鄰居信息表Neighbor Table（a），同時(shí)，節(jié)點(diǎn)c發(fā)現(xiàn)其鄰居節(jié)點(diǎn)a并將自己的鄰居信息表Neighbor Table（c）。至此，節(jié)點(diǎn)a完成了對(duì)節(jié)點(diǎn)b和節(jié)點(diǎn)c的鄰居發(fā)現(xiàn)過(guò)程，節(jié)點(diǎn)a將節(jié)點(diǎn)b和c的信息添加到鄰居表中。當(dāng)t=64時(shí)，節(jié)點(diǎn)a、b和c才同時(shí)處于蘇醒狀態(tài)。

2 設(shè)計(jì)原理

圖2 傳感器網(wǎng)絡(luò)鄰居發(fā)現(xiàn)算法-Disco算法原理圖

如圖2所示，以傳感器網(wǎng)絡(luò)中的a，b，c三個(gè)節(jié)點(diǎn)為例，其中節(jié)點(diǎn)a為發(fā)現(xiàn)節(jié)點(diǎn)DN，節(jié)點(diǎn)a，b和c都按照各自的工作安排進(jìn)行調(diào)度。在t=1時(shí)，節(jié)點(diǎn)b和節(jié)點(diǎn)c同時(shí)處于喚醒狀態(tài)（Active State），節(jié)點(diǎn)b和c發(fā)現(xiàn)彼此，并將其添加到彼此的鄰居表Neighbor Table（b）和Neighbor Table（c）中；在t=4時(shí)，節(jié)點(diǎn)b和節(jié)點(diǎn)a同時(shí)處于喚醒狀態(tài)，它們發(fā)現(xiàn)彼此，并將對(duì)方加入到自己的鄰居表Neighbor Table（b）和Neighbor Table（a）中。此時(shí)節(jié)點(diǎn)a和節(jié)點(diǎn)b互為鄰居節(jié)點(diǎn)，節(jié)點(diǎn)b和節(jié)點(diǎn)c互為鄰居節(jié)點(diǎn)，但是節(jié)點(diǎn)a和節(jié)點(diǎn)c并沒(méi)有發(fā)彼此，因而無(wú)法判斷是否是鄰居節(jié)點(diǎn)。當(dāng)時(shí)間t=29時(shí)，節(jié)點(diǎn)a和節(jié)點(diǎn)c同時(shí)處于蘇醒狀態(tài)，接節(jié)點(diǎn)a現(xiàn)其鄰居節(jié)點(diǎn)c并

低延遲鄰居發(fā)現(xiàn)算法Group的原理：

（1）對(duì)于傳感器網(wǎng)絡(luò)中一個(gè)單獨(dú)的節(jié)點(diǎn)，節(jié)點(diǎn)根據(jù)自己的工作調(diào)度安排，周期性地處于喚醒狀態(tài)和睡眠狀態(tài)。此時(shí)，節(jié)點(diǎn)將自己的工作安排調(diào)度進(jìn)行廣播；

（2）當(dāng)傳感器網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)同時(shí)處于喚醒狀態(tài)時(shí)，一個(gè)節(jié)點(diǎn)發(fā)現(xiàn)了另外一個(gè)節(jié)點(diǎn)時(shí)，這兩個(gè)節(jié)點(diǎn)便形成一個(gè)虛擬組。當(dāng)?shù)谌齻€(gè)節(jié)點(diǎn)與第一個(gè)節(jié)點(diǎn)同時(shí)喚醒時(shí)，第三個(gè)節(jié)點(diǎn)發(fā)現(xiàn)第一個(gè)節(jié)點(diǎn)并將其加入到自己的鄰居表中；

（3）第一個(gè)節(jié)點(diǎn)在第三個(gè)節(jié)點(diǎn)喚醒時(shí)隙主動(dòng)蘇醒，將其發(fā)現(xiàn)的鄰居節(jié)點(diǎn)信息（第二個(gè)節(jié)點(diǎn)）廣播給第三個(gè)節(jié)點(diǎn)；

（4）第三個(gè)節(jié)點(diǎn)在第二個(gè)節(jié)點(diǎn)喚醒時(shí)隙時(shí)主動(dòng)喚醒，由于第三個(gè)節(jié)點(diǎn)通過(guò)第一個(gè)節(jié)點(diǎn)已經(jīng)獲知第二個(gè)節(jié)點(diǎn)的信息，此時(shí)只需判斷這個(gè)節(jié)點(diǎn)是否是其鄰居節(jié)點(diǎn)，如果是的話，將其加入到自己的鄰居表中，形成一個(gè)更大的虛擬組。以此類推，這個(gè)由鄰居節(jié)點(diǎn)組成的組不斷地?cái)U(kuò)大，從而完成鄰居節(jié)點(diǎn)的發(fā)現(xiàn)。

3 度量標(biāo)準(zhǔn)

同步鄰居發(fā)現(xiàn)算法在部署節(jié)點(diǎn)時(shí)要求所有的節(jié)點(diǎn)擁有相同的初始化時(shí)間，但是這樣的要求在實(shí)際的應(yīng)用環(huán)境中很難實(shí)現(xiàn)，或者基本上不可能，所以這里我們主要針對(duì)異步鄰居發(fā)現(xiàn)算法提出鄰居發(fā)現(xiàn)算法的度量標(biāo)準(zhǔn)，這個(gè)標(biāo)準(zhǔn)對(duì)于同步鄰居發(fā)現(xiàn)算法還是具有一定的參考意義的。

能量的高效性以及較低的發(fā)現(xiàn)延遲是評(píng)價(jià)鄰居發(fā)現(xiàn)算法的兩個(gè)主要參數(shù)，通過(guò)這個(gè)參數(shù)的分析比較基本上可以確定某個(gè)鄰居發(fā)現(xiàn)算法是否具有實(shí)用性。在實(shí)際情況中，既要提高能量的有效性，又要擁有較低的發(fā)現(xiàn)延遲，這是不可能的，魚(yú)和熊掌不可兼得。在本文進(jìn)行研究之前，已經(jīng)有部分人將研究方向投向鄰居發(fā)現(xiàn)，分析發(fā)現(xiàn)這些研究成果都有一個(gè)共同點(diǎn)：以犧牲節(jié)點(diǎn)的能量來(lái)?yè)Q取較低的發(fā)現(xiàn)延遲或者以較高的發(fā)現(xiàn)延遲來(lái)節(jié)省節(jié)點(diǎn)的能量，所以鄰居發(fā)現(xiàn)的一個(gè)主要目標(biāo)就是在節(jié)點(diǎn)的能耗和發(fā)現(xiàn)延遲兩個(gè)方面尋求一個(gè)最佳的平衡點(diǎn)，一味地追求高能效、低延遲是與現(xiàn)實(shí)情況相悖的。

為了更好地評(píng)價(jià)一個(gè)鄰居發(fā)現(xiàn)算法的好壞，是否具有一定的實(shí)際意義，我們將采用能耗-延遲（Power-Latency，PL）的乘積M來(lái)作為鄰居發(fā)現(xiàn)算法的評(píng)價(jià)標(biāo)準(zhǔn)。

對(duì)于周期為T的鄰居發(fā)現(xiàn)調(diào)度滿足如下關(guān)系：

則一個(gè)調(diào)度周期內(nèi)的平均能耗P表示為：

在這個(gè)周期為T的鄰居發(fā)現(xiàn)調(diào)度中，假設(shè)所有成對(duì)節(jié)點(diǎn)（節(jié)點(diǎn)賦予所有可能的相對(duì)相位偏移量）中最差的發(fā)現(xiàn)延遲為L(zhǎng)，則我們將能耗-延遲的乘積M定義為：

采用時(shí)隙調(diào)度機(jī)制有以下兩個(gè)優(yōu)點(diǎn)：第一，時(shí)隙調(diào)度機(jī)制是可以實(shí)際實(shí)現(xiàn)的；第二，只要節(jié)點(diǎn)的時(shí)鐘漂移總和小于單個(gè)時(shí)隙的長(zhǎng)度，時(shí)隙參考機(jī)制就可以克服時(shí)鐘漂移問(wèn)題。

在延遲需求為L(zhǎng)的鄰居發(fā)現(xiàn)中，時(shí)隙長(zhǎng)度要比L單位時(shí)間內(nèi)最差情況下的相對(duì)時(shí)間漂移大。同時(shí)，一個(gè)時(shí)間槽持續(xù)時(shí)間的設(shè)定與很多實(shí)現(xiàn)因素相關(guān)，比如，無(wú)線電在切換接收狀態(tài)和發(fā)送狀態(tài)的周轉(zhuǎn)周期、將振蕩器從低功耗狀態(tài)加速需要的時(shí)間以及清空信道需要的時(shí)間等。由于實(shí)際鄰居發(fā)現(xiàn)算法的槽性質(zhì)，發(fā)現(xiàn)調(diào)度是離散性質(zhì)的，所以這里我們用表示離散狀態(tài)下的發(fā)現(xiàn)調(diào)度，滿足延遲需求L的周期為T的節(jié)點(diǎn)m在時(shí)隙t時(shí)的發(fā)現(xiàn)調(diào)度可表示為，同時(shí)一個(gè)周期內(nèi)的平均能耗P為：

則能耗-延遲乘積M為：

4 結(jié)語(yǔ)

本文在研究已有鄰居發(fā)現(xiàn)算法的基礎(chǔ)上，對(duì)各算法之間的區(qū)別與聯(lián)系作深入分析，并開(kāi)始著手鄰居發(fā)現(xiàn)問(wèn)題方面的研究，主要在以下幾個(gè)方面進(jìn)行深入研究：

（1）分析并挖掘延遲更低的自適應(yīng)鄰居發(fā)現(xiàn)調(diào)度算法。在無(wú)線傳感器網(wǎng)絡(luò)中，兩個(gè)節(jié)點(diǎn)實(shí)現(xiàn)鄰居發(fā)現(xiàn)的一個(gè)基本條件就是節(jié)點(diǎn)必須處在彼此的通信范圍內(nèi)，只有這樣節(jié)點(diǎn)之間才能夠正常通信，并完成數(shù)據(jù)傳輸。目前，在學(xué)術(shù)界的經(jīng)常討論和研究的熱點(diǎn)算法基本上都是經(jīng)典的成對(duì)發(fā)現(xiàn)（如Disco、U-Connect），即傳感器網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)分別根據(jù)自己的工作安排調(diào)度蘇醒，如果兩個(gè)節(jié)點(diǎn)的蘇醒時(shí)隙重疊（即同時(shí)蘇醒），而且在彼此的通信范圍內(nèi)，則這兩個(gè)節(jié)點(diǎn)就可以互相發(fā)現(xiàn)互為鄰居，同時(shí)添加到各自的鄰居表中。仔細(xì)分析不難發(fā)現(xiàn)，這一類的發(fā)現(xiàn)策略沒(méi)有充分利用節(jié)點(diǎn)的時(shí)間相關(guān)性這一特性。綜合考慮節(jié)點(diǎn)間的時(shí)間相關(guān)性，采用主動(dòng)蘇醒的Demand-Wakeup機(jī)制，根據(jù)已有鄰居節(jié)點(diǎn)獲取潛在鄰居節(jié)點(diǎn)的信息，通過(guò)主動(dòng)蘇醒來(lái)發(fā)現(xiàn)潛在的鄰居節(jié)點(diǎn)，并在此基礎(chǔ)上研究鄰居節(jié)點(diǎn)間信息的推薦機(jī)制，提出基于公共鄰居率的鄰居推薦機(jī)制，通過(guò)該推薦機(jī)制，使得CNR-Group算法在延遲和能耗方面都有所降低，提升了網(wǎng)絡(luò)的性能，延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

（2）利用實(shí)際的節(jié)點(diǎn)移動(dòng)模型來(lái)預(yù)測(cè)潛在的鄰居節(jié)點(diǎn)，并通過(guò)潛在的鄰居節(jié)點(diǎn)數(shù)動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的占空比，以此提高鄰居節(jié)點(diǎn)的發(fā)現(xiàn)效率，降低發(fā)現(xiàn)延遲。根據(jù)所交換的節(jié)點(diǎn)調(diào)度信息主動(dòng)蘇醒可以實(shí)現(xiàn)鄰居節(jié)點(diǎn)的發(fā)現(xiàn)。

（3）根據(jù)節(jié)點(diǎn)的移動(dòng)模型可以估計(jì)節(jié)點(diǎn)的位置，節(jié)點(diǎn)可以預(yù)估其通信范圍內(nèi)潛在的鄰居節(jié)點(diǎn)個(gè)數(shù)，如果鄰居節(jié)點(diǎn)的個(gè)數(shù)超過(guò)所設(shè)定的閾值，節(jié)點(diǎn)動(dòng)態(tài)調(diào)節(jié)占空比并延長(zhǎng)蘇醒時(shí)間，來(lái)實(shí)現(xiàn)更多節(jié)點(diǎn)的鄰居發(fā)現(xiàn)。

[1]Mc Glynn M J，Borbash S A.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks.Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking&Computing[C].ACM，2001.

[2]Borbash S A，Ephremides A，Mc Glynn M J.An Asynchronous Neighbor Discovery Algorithm for Wireless Sensor Networks[J].Ad Hoc Networks，2007，5（7）:998-1016.

[3]Lai S，Ravindran B，Cho H.Heterogenous Quorum-Based Wake-up Scheduling in Wireless Sensor Networks[J].Computers，IEEE Transactions on，2010，59（11）:1562-1575.

[4]Dutta P，Culler D.Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications.Proceedings of the 6th ACM conference on Embedded Network Sensor Systems[C].ACM，2008.

[5]Kandhalu A，Lakshmanan K，Rajkumar R R.U-connect:a Low-Latency Energy-Efficient Asynchronous Neighbor Discovery Protocol. Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks[C].ACM，2010.

[6]Karowski N，Viana A C，Wolisz A.Optimized Asynchronous Multi-Channel Neighbor Discovery.INFOCOM，2011 Proceedings IEEE [C].IEEE，2011.

[7]Niven I，Zuckerman H S，Montgomery H L.An Introduction to the Theory of Numbers[M].John Wiley&Sons，2008.

[8]Chen L，Gu Y，Guo S，et al.Group-Based Discovery in Low-Duty-Cycle Mobile Sensor Networks.Sensor，Mesh and Ad Hoc Communications and Networks SECON），2012 9th Annual IEEE Communications Society Conference on[C].IEEE，2012.

Research on a Low Latency Neighbor Discovery Algorithm for Wireless Sensor Network

LIU Yuan-zi

（College of Computer Science，Sichuan University，Chengdu 610065）

Neighbors discovery problem is wireless sensor networks(WSNs)one of the important part of communication protocol.As it needs not synchronization communication,asynchronous neighbor discovery algorithm got more attention in recent years.For asynchronous network environment,designs a novel neighbor discovery algorithm,and validates its discovery latency and energy consumption in different case such as node density,node duty cycle,node communications irregular degree and node move mode.The results show that the algorithm has achieved good results in reducing discovery delay,and improves the network performance,and has a high practical value in higher re-al-time requirement wireless sensor network.

Neighbor Discovery;Dynamic Duty Cycle;Discovery Latency

1007-1423（2016）08-0016-05

10.3969/j.issn.1007-1423.2016.08.003

劉元梓（1984-），男，重慶云陽(yáng)人，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)信息安全

2016-03-01

2016-03-10