劉元梓
(四川大學計算機學院,成都 610065)
無線傳感器網(wǎng)絡(luò)低延遲鄰居發(fā)現(xiàn)算法研究
劉元梓
(四川大學計算機學院,成都 610065)
鄰居發(fā)現(xiàn)問題是無線傳感器網(wǎng)絡(luò)(WSNs)通信協(xié)議的重要組成部分之一。由于不需要同步通訊,異步的鄰居發(fā)現(xiàn)算法近年得到較多的關(guān)注。針對異步網(wǎng)絡(luò)環(huán)境,設(shè)計一種新穎的鄰居發(fā)現(xiàn)算法,并驗證在不同節(jié)點密度、節(jié)點占空比、節(jié)點通信不規(guī)則度以及節(jié)點移動方式等情況下,該算法的發(fā)現(xiàn)延遲和能耗。結(jié)果表明,該算法在降低發(fā)現(xiàn)延遲方面取得良好效果,提升網(wǎng)絡(luò)的性能,對實時性要求較高的無線傳感器網(wǎng)絡(luò)有很高的實用價值。
鄰居發(fā)現(xiàn);動態(tài)占空比;發(fā)現(xiàn)延遲
鄰居發(fā)現(xiàn)同時間同步、節(jié)點定位等一樣,是無線傳感器網(wǎng)絡(luò)的基礎(chǔ)支撐技術(shù)。鄰居發(fā)現(xiàn)對于節(jié)點識別周邊環(huán)境的鄰居節(jié)點以及構(gòu)建路由并協(xié)同工作,具有重要意義。無線傳感器網(wǎng)絡(luò)經(jīng)過多年的研究發(fā)展,鄰居發(fā)現(xiàn)已不再是一項新的技術(shù),具有一定量的可參考文獻資料。一直處于喚醒狀態(tài)的節(jié)點發(fā)現(xiàn)的研究主要集中在定向天線,而基于占空比的節(jié)點發(fā)現(xiàn)算法則是多種多樣的。當傳感器節(jié)點處于移動的環(huán)境中,這種環(huán)境對發(fā)現(xiàn)時間有很高要求,即要以盡可能快地速度發(fā)現(xiàn)節(jié)點。
比較著名的傳感器節(jié)點發(fā)現(xiàn)算法有Stochasticbased Protocols[1-2],Quorum-based Protocols[3],Disco[4],UConnect[5],多信道[6]以及基于沖突的節(jié)點發(fā)現(xiàn)等。這些算法主要集中在怎樣通過某一類型的調(diào)度算法來保證一對節(jié)點可以同時喚醒,經(jīng)過驗證這些算法是有效的,可以保證節(jié)點在有限的時間界限內(nèi)發(fā)現(xiàn)其鄰居節(jié)點。Stochastic-based Protocols中,節(jié)點以隨機循環(huán)的方式監(jiān)聽、傳輸或者休眠,在耗能和發(fā)現(xiàn)延遲上進行權(quán)衡折中。Quorum-based Protocols闡明在有界限的時間上保證成對節(jié)點的喚醒時間重疊的局限性。Disco介紹了一個基于中國剩余定理(Chinese Reminder Theorem)的鄰居發(fā)現(xiàn)算法,算法中節(jié)點選擇一對素數(shù)作為周期,素數(shù)的選擇要滿足其占空比要求。U-Connect提出了針對對稱或者非對稱的占空比設(shè)置的統(tǒng)一鄰居發(fā)現(xiàn)算法。值得注意的是U-Connect對于對稱異步的發(fā)現(xiàn)方案是1.5倍近似算法,而Quorum和Disco則是2倍近似算法。
在傳統(tǒng)的成對發(fā)現(xiàn)算法中,每個節(jié)點周期性地處于喚醒狀態(tài)和休眠狀態(tài),而且傳感器網(wǎng)絡(luò)中鄰居節(jié)點必須是處于彼此的通信范圍之內(nèi)的,只有這樣節(jié)點之間才可以正常通信,進而實現(xiàn)數(shù)據(jù)的傳輸。當兩個節(jié)點分別根據(jù)自己的工作安排進行調(diào)度并同時處于喚醒狀態(tài)時,兩個節(jié)點此發(fā)現(xiàn)對方,并將對方加入到自己的鄰居表中,至此完成了一個鄰居節(jié)點的發(fā)現(xiàn)。組發(fā)現(xiàn)算法,同成對發(fā)現(xiàn)算法一樣,節(jié)點是在喚醒狀態(tài)和休眠狀態(tài)之間周期性地切換。傳感器網(wǎng)絡(luò)節(jié)點處于蘇醒狀態(tài)時,根據(jù)自己的工作安排調(diào)度進行廣播;當傳感器網(wǎng)絡(luò)中的兩個節(jié)點同時處于喚醒狀態(tài)并在彼此的通信范圍內(nèi)時,一個節(jié)點發(fā)現(xiàn)了另外一個節(jié)點,這兩個節(jié)點便形成一個組。當?shù)谌齻€節(jié)點與第一個節(jié)點同時喚醒時,第三個節(jié)點發(fā)現(xiàn)第一個節(jié)點并將其加入到自己的鄰居表中,同時第一個節(jié)點將其發(fā)現(xiàn)的鄰居節(jié)點信息廣播給第三個節(jié)點;當?shù)谌齻€節(jié)點和第二個節(jié)點的喚醒時間同步時,由于第三個節(jié)點通過第一個節(jié)點已經(jīng)獲知第二個節(jié)點的信息,此時只需判斷這個節(jié)點是否是其鄰居節(jié)點,如果是的話,將其加入到自己的鄰居表中,形成一個更大的組。以此類推,這個由鄰居節(jié)點組成的組不斷地擴大,從而完成鄰居節(jié)點的發(fā)現(xiàn)。
本文的主要貢獻如下所示:
(1)根據(jù)影響無線傳感器網(wǎng)絡(luò)能量消耗和延遲的因素,分析現(xiàn)有的鄰居發(fā)現(xiàn)算法的優(yōu)缺點,研究性能更優(yōu)、延遲更低的鄰居發(fā)現(xiàn)算法;
(2)分析已有鄰居發(fā)現(xiàn)算法中節(jié)點的調(diào)度機制,采取更先進的發(fā)現(xiàn)調(diào)度策略。鄰居發(fā)現(xiàn)策略采用群組發(fā)現(xiàn)的思想,所有節(jié)點采用周期性的睡眠調(diào)度機制,發(fā)現(xiàn)節(jié)點將已發(fā)現(xiàn)的鄰居節(jié)點納入其所在的群組,通過已有鄰居節(jié)點的鄰居信息來獲取潛在的鄰居節(jié)點的信息,采用Demand-wakeup機制主動蘇醒以更快的速度發(fā)現(xiàn)更多的鄰居節(jié)點;
(3)研究群組發(fā)現(xiàn)過程中節(jié)點間信息的推薦機制,鄰居節(jié)點如何有效地向發(fā)現(xiàn)節(jié)點推薦潛在的鄰居信息來保證發(fā)現(xiàn)效率的同時降低能耗以及發(fā)現(xiàn)節(jié)點如何高效選擇鄰居節(jié)點的信息避免過多接收無用的信息而造成不必要的能耗;
(4)利用傳感器網(wǎng)絡(luò)中節(jié)點移動模型預(yù)測節(jié)點通信范圍內(nèi)潛在的鄰居節(jié)點,根據(jù)潛在的鄰居節(jié)點的數(shù)量動態(tài)調(diào)整節(jié)點的占空比,以此更快更多地發(fā)現(xiàn)鄰居節(jié)點;
本文剩余部分的內(nèi)容主要是算法的設(shè)計與實現(xiàn)。
路由器、交換機等硬件設(shè)備,那么無線傳感器網(wǎng)絡(luò)中的節(jié)點如何通信呢?毫無疑問,所有的工作都是由傳感器節(jié)點自身來完成。
許多應(yīng)用設(shè)備,包括那些布置在廣闊野外區(qū)域的具有多樣性配置的設(shè)備,例如在野外部署的低廉傳感器,主要用于環(huán)境監(jiān)測、野生動物監(jiān)測、戰(zhàn)場環(huán)境監(jiān)視以及采集野外環(huán)境信息等。如何精確保證這些傳感器節(jié)點的全局時間同步是個具有挑戰(zhàn)性的問題,為了解決這個問題,通常采用基于分布式協(xié)調(diào)占空比模式來決定各自的工作調(diào)度,即由節(jié)點自己的工作調(diào)度決定何時工作、何時發(fā)送數(shù)據(jù)、何時接收數(shù)據(jù)以及何時進入低功耗的休眠狀態(tài)。
為了安排節(jié)點的工作調(diào)度,我們將傳感器設(shè)備(如節(jié)點S)的工作時間劃分為連續(xù)的固定長度的時隙(Time Slots),依據(jù)預(yù)先安裝的協(xié)議,節(jié)點S激活無線電設(shè)備并將其狀態(tài)在某一段時隙內(nèi)切換至發(fā)現(xiàn)模式,然后節(jié)點S向網(wǎng)絡(luò)中的并且處于其通信范圍內(nèi)的其他節(jié)點廣播消息,以此來通知它的存在性,同時節(jié)點S也偵聽其他節(jié)點的信息。如果在某一時隙,節(jié)點S和其他的節(jié)點同時處于工作狀態(tài),即工作調(diào)度出現(xiàn)重疊部分,如果節(jié)點在彼此的通信范圍內(nèi),它們就能夠互相發(fā)現(xiàn)并成為彼此的鄰居節(jié)點。
定義1:我們通常將上述在時間方面的調(diào)度機制成為時隙參考機制(Time Slots Reference Mechanism)。
時隙參考機制的示意圖如圖1所示。
圖1 時隙參考機制示意圖
無線傳感器網(wǎng)絡(luò)中所有節(jié)點在網(wǎng)絡(luò)中地位是同等的,任何一個節(jié)點既是發(fā)送節(jié)點也是接收節(jié)點,將自己采集和接收的數(shù)據(jù)信息傳送給離接收者更近的節(jié)點以及向網(wǎng)絡(luò)中的其他節(jié)點廣播從而將其存在性通知給其他節(jié)點;同時,接收來自于其他節(jié)點發(fā)送的數(shù)據(jù)信息。無線傳感器網(wǎng)絡(luò)沒有固定的用于發(fā)送和接收信息的基礎(chǔ)設(shè)施,不具有手持設(shè)備(如手機等)固定的用于轉(zhuǎn)接信號的信號接收塔和發(fā)送塔,也不具有Internet的專用
在圖1中,我們將節(jié)點的工作周期劃分為蘇醒狀態(tài)(Active State)和休眠狀態(tài)(Dormant State),圖中,我們用黑色區(qū)域時隙代表蘇醒狀態(tài),白色區(qū)域時隙代表休眠狀態(tài),如果有兩個或多個節(jié)點同時處于蘇醒狀態(tài)(或者說工作調(diào)度出現(xiàn)重疊),而且彼此之間可以互相通信,它們之間就可以完成鄰居發(fā)現(xiàn),成為彼此的鄰居節(jié)點。
Dutta和Culler在文獻[4]中提出異步鄰居發(fā)現(xiàn)算法Disco,該算法基于中國剩余定理相關(guān)理論,算法中兩個節(jié)點選擇一對素數(shù),使得這兩個素數(shù)的倒數(shù)分別與節(jié)點期望的占空比相等,采取素數(shù)的好處是可以保證兩個節(jié)點在工作過程中會出現(xiàn)相同的喚醒時隙,使得節(jié)點間可以相互通信并完成鄰居發(fā)現(xiàn)。在Disco算法中,所有的節(jié)點采取周期性偵聽-睡眠機制,周期性地在蘇醒狀態(tài)(Active State)和休眠狀態(tài)(Dormant State)或者睡眠狀態(tài)(Sleep State)間切換。鄰居發(fā)現(xiàn)的過程如下:網(wǎng)絡(luò)中一個節(jié)點處于另一個節(jié)點的通信范圍內(nèi),并且在某一時刻這兩個節(jié)點同時處于蘇醒狀態(tài),如果一個節(jié)點的無線電廣播信息時,由于另一個節(jié)點處于蘇醒狀態(tài)可以接收到廣播信息,此時,兩個節(jié)點交換數(shù)據(jù)信息,完成鄰居發(fā)現(xiàn),成為彼此的鄰居節(jié)點。Disco算法的原理如圖2所示。將其加入自己的鄰居信息表Neighbor Table(a),同時,節(jié)點c發(fā)現(xiàn)其鄰居節(jié)點a并將自己的鄰居信息表Neighbor Table(c)。至此,節(jié)點a完成了對節(jié)點b和節(jié)點c的鄰居發(fā)現(xiàn)過程,節(jié)點a將節(jié)點b和c的信息添加到鄰居表中。當t=64時,節(jié)點a、b和c才同時處于蘇醒狀態(tài)。
圖2 傳感器網(wǎng)絡(luò)鄰居發(fā)現(xiàn)算法-Disco算法原理圖
如圖2所示,以傳感器網(wǎng)絡(luò)中的a,b,c三個節(jié)點為例,其中節(jié)點a為發(fā)現(xiàn)節(jié)點DN,節(jié)點a,b和c都按照各自的工作安排進行調(diào)度。在t=1時,節(jié)點b和節(jié)點c同時處于喚醒狀態(tài)(Active State),節(jié)點b和c發(fā)現(xiàn)彼此,并將其添加到彼此的鄰居表Neighbor Table(b)和Neighbor Table(c)中;在t=4時,節(jié)點b和節(jié)點a同時處于喚醒狀態(tài),它們發(fā)現(xiàn)彼此,并將對方加入到自己的鄰居表Neighbor Table(b)和Neighbor Table(a)中。此時節(jié)點a和節(jié)點b互為鄰居節(jié)點,節(jié)點b和節(jié)點c互為鄰居節(jié)點,但是節(jié)點a和節(jié)點c并沒有發(fā)彼此,因而無法判斷是否是鄰居節(jié)點。當時間t=29時,節(jié)點a和節(jié)點c同時處于蘇醒狀態(tài),接節(jié)點a現(xiàn)其鄰居節(jié)點c并
低延遲鄰居發(fā)現(xiàn)算法Group的原理:
(1)對于傳感器網(wǎng)絡(luò)中一個單獨的節(jié)點,節(jié)點根據(jù)自己的工作調(diào)度安排,周期性地處于喚醒狀態(tài)和睡眠狀態(tài)。此時,節(jié)點將自己的工作安排調(diào)度進行廣播;
(2)當傳感器網(wǎng)絡(luò)中的兩個節(jié)點同時處于喚醒狀態(tài)時,一個節(jié)點發(fā)現(xiàn)了另外一個節(jié)點時,這兩個節(jié)點便形成一個虛擬組。當?shù)谌齻€節(jié)點與第一個節(jié)點同時喚醒時,第三個節(jié)點發(fā)現(xiàn)第一個節(jié)點并將其加入到自己的鄰居表中;
(3)第一個節(jié)點在第三個節(jié)點喚醒時隙主動蘇醒,將其發(fā)現(xiàn)的鄰居節(jié)點信息(第二個節(jié)點)廣播給第三個節(jié)點;
(4)第三個節(jié)點在第二個節(jié)點喚醒時隙時主動喚醒,由于第三個節(jié)點通過第一個節(jié)點已經(jīng)獲知第二個節(jié)點的信息,此時只需判斷這個節(jié)點是否是其鄰居節(jié)點,如果是的話,將其加入到自己的鄰居表中,形成一個更大的虛擬組。以此類推,這個由鄰居節(jié)點組成的組不斷地擴大,從而完成鄰居節(jié)點的發(fā)現(xiàn)。
同步鄰居發(fā)現(xiàn)算法在部署節(jié)點時要求所有的節(jié)點擁有相同的初始化時間,但是這樣的要求在實際的應(yīng)用環(huán)境中很難實現(xiàn),或者基本上不可能,所以這里我們主要針對異步鄰居發(fā)現(xiàn)算法提出鄰居發(fā)現(xiàn)算法的度量標準,這個標準對于同步鄰居發(fā)現(xiàn)算法還是具有一定的參考意義的。
能量的高效性以及較低的發(fā)現(xiàn)延遲是評價鄰居發(fā)現(xiàn)算法的兩個主要參數(shù),通過這個參數(shù)的分析比較基本上可以確定某個鄰居發(fā)現(xiàn)算法是否具有實用性。在實際情況中,既要提高能量的有效性,又要擁有較低的發(fā)現(xiàn)延遲,這是不可能的,魚和熊掌不可兼得。在本文進行研究之前,已經(jīng)有部分人將研究方向投向鄰居發(fā)現(xiàn),分析發(fā)現(xiàn)這些研究成果都有一個共同點:以犧牲節(jié)點的能量來換取較低的發(fā)現(xiàn)延遲或者以較高的發(fā)現(xiàn)延遲來節(jié)省節(jié)點的能量,所以鄰居發(fā)現(xiàn)的一個主要目標就是在節(jié)點的能耗和發(fā)現(xiàn)延遲兩個方面尋求一個最佳的平衡點,一味地追求高能效、低延遲是與現(xiàn)實情況相悖的。
為了更好地評價一個鄰居發(fā)現(xiàn)算法的好壞,是否具有一定的實際意義,我們將采用能耗-延遲(Power-Latency,PL)的乘積M來作為鄰居發(fā)現(xiàn)算法的評價標準。
對于周期為T的鄰居發(fā)現(xiàn)調(diào)度滿足如下關(guān)系:
則一個調(diào)度周期內(nèi)的平均能耗P表示為:
在這個周期為T的鄰居發(fā)現(xiàn)調(diào)度中,假設(shè)所有成對節(jié)點(節(jié)點賦予所有可能的相對相位偏移量)中最差的發(fā)現(xiàn)延遲為L,則我們將能耗-延遲的乘積M定義為:
采用時隙調(diào)度機制有以下兩個優(yōu)點:第一,時隙調(diào)度機制是可以實際實現(xiàn)的;第二,只要節(jié)點的時鐘漂移總和小于單個時隙的長度,時隙參考機制就可以克服時鐘漂移問題。
在延遲需求為L的鄰居發(fā)現(xiàn)中,時隙長度要比L單位時間內(nèi)最差情況下的相對時間漂移大。同時,一個時間槽持續(xù)時間的設(shè)定與很多實現(xiàn)因素相關(guān),比如,無線電在切換接收狀態(tài)和發(fā)送狀態(tài)的周轉(zhuǎn)周期、將振蕩器從低功耗狀態(tài)加速需要的時間以及清空信道需要的時間等。由于實際鄰居發(fā)現(xiàn)算法的槽性質(zhì),發(fā)現(xiàn)調(diào)度是離散性質(zhì)的,所以這里我們用表示離散狀態(tài)下的發(fā)現(xiàn)調(diào)度,滿足延遲需求L的周期為T的節(jié)點m在時隙t時的發(fā)現(xiàn)調(diào)度可表示為,同時一個周期內(nèi)的平均能耗P為:
則能耗-延遲乘積M為:
本文在研究已有鄰居發(fā)現(xiàn)算法的基礎(chǔ)上,對各算法之間的區(qū)別與聯(lián)系作深入分析,并開始著手鄰居發(fā)現(xiàn)問題方面的研究,主要在以下幾個方面進行深入研究:
(1)分析并挖掘延遲更低的自適應(yīng)鄰居發(fā)現(xiàn)調(diào)度算法。在無線傳感器網(wǎng)絡(luò)中,兩個節(jié)點實現(xiàn)鄰居發(fā)現(xiàn)的一個基本條件就是節(jié)點必須處在彼此的通信范圍內(nèi),只有這樣節(jié)點之間才能夠正常通信,并完成數(shù)據(jù)傳輸。目前,在學術(shù)界的經(jīng)常討論和研究的熱點算法基本上都是經(jīng)典的成對發(fā)現(xiàn)(如Disco、U-Connect),即傳感器網(wǎng)絡(luò)中的兩個節(jié)點分別根據(jù)自己的工作安排調(diào)度蘇醒,如果兩個節(jié)點的蘇醒時隙重疊(即同時蘇醒),而且在彼此的通信范圍內(nèi),則這兩個節(jié)點就可以互相發(fā)現(xiàn)互為鄰居,同時添加到各自的鄰居表中。仔細分析不難發(fā)現(xiàn),這一類的發(fā)現(xiàn)策略沒有充分利用節(jié)點的時間相關(guān)性這一特性。綜合考慮節(jié)點間的時間相關(guān)性,采用主動蘇醒的Demand-Wakeup機制,根據(jù)已有鄰居節(jié)點獲取潛在鄰居節(jié)點的信息,通過主動蘇醒來發(fā)現(xiàn)潛在的鄰居節(jié)點,并在此基礎(chǔ)上研究鄰居節(jié)點間信息的推薦機制,提出基于公共鄰居率的鄰居推薦機制,通過該推薦機制,使得CNR-Group算法在延遲和能耗方面都有所降低,提升了網(wǎng)絡(luò)的性能,延長了網(wǎng)絡(luò)的生命周期。
(2)利用實際的節(jié)點移動模型來預(yù)測潛在的鄰居節(jié)點,并通過潛在的鄰居節(jié)點數(shù)動態(tài)調(diào)整節(jié)點的占空比,以此提高鄰居節(jié)點的發(fā)現(xiàn)效率,降低發(fā)現(xiàn)延遲。根據(jù)所交換的節(jié)點調(diào)度信息主動蘇醒可以實現(xiàn)鄰居節(jié)點的發(fā)現(xiàn)。
(3)根據(jù)節(jié)點的移動模型可以估計節(jié)點的位置,節(jié)點可以預(yù)估其通信范圍內(nèi)潛在的鄰居節(jié)點個數(shù),如果鄰居節(jié)點的個數(shù)超過所設(shè)定的閾值,節(jié)點動態(tài)調(diào)節(jié)占空比并延長蘇醒時間,來實現(xiàn)更多節(jié)點的鄰居發(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-),男,重慶云陽人,碩士研究生,研究方向為網(wǎng)絡(luò)信息安全
2016-03-01
2016-03-10