無線納米傳感網(wǎng)中基于概率的洪泛算法*

夏建川，張秀娟，王斯鋒

（曲阜師范大學 信息科學與工程學院，山東 日照 276826）

0 引 言

無線傳感器網(wǎng)絡在軍事和民用領(lǐng)域都具有重要的應用前景[1]。納米技術(shù)允許納米器件以納米尺度收集，創(chuàng)建，計算，處理和傳輸數(shù)據(jù)。因此，采用納米技術(shù)的無線納米傳感網(wǎng)能為健康監(jiān)測、智慧城市、軍事、農(nóng)業(yè)和工業(yè)等眾多應用提供新的解決方案。納米節(jié)點具有能量有限、節(jié)點資源受限、分布性和多跳通信等特點。

基于電磁的納米傳感器是適合建立無線納米傳感網(wǎng)的器件。它使用基于石墨烯的天線，擁有納米收發(fā)器，能夠在0.1～10 THz波段傳輸和接收電磁波[2]。這種通信能力使得納米傳感器能夠以同步、監(jiān)督和合作的方式工作，實現(xiàn)共同的任務。當納米傳感器互聯(lián)時，構(gòu)成無線納米傳感網(wǎng)，可以使用廣播和通信協(xié)議來控制它們。資源有限的納米傳感器之間可以用洪泛協(xié)議傳播數(shù)據(jù)，但由于過多的數(shù)據(jù)包重傳會浪費帶寬，加大消耗能量。因此減少冗余傳輸是需要解決的主要問題之一。

本文第2節(jié)列出相關(guān)工作；第3節(jié)給出能減少冗余傳輸?shù)脑敿毸惴ǎ坏?節(jié)是仿真結(jié)果及性能分析，并指出下一步工作方向。

1 相關(guān)工作

納米傳感器非常小，至多幾百納米，存儲能力也有限。因此，納米傳感器沒有存儲路由表的存儲能力，也沒有查找路由表的處理能力。限于納米傳感器的存儲、處理、能量的有限性，傳統(tǒng)的路由協(xié)議不適于無線納米傳感網(wǎng)，簡單的路由算法洪泛是合適的。洪泛算法中，每個節(jié)點將自己收到的數(shù)據(jù)包，廣播給除了源節(jié)點之外的其它（傳輸范圍內(nèi)的）所有節(jié)點。它可以應用于無線納米傳感網(wǎng)，但直接的洪泛算法會引起廣播風暴問題，導致大量數(shù)據(jù)包重傳，丟失，造成沖突，增大消耗。許多學者通過分析或者仿真研究了廣播風暴問題的危害[3]。文獻[4]中針對納米傳感器沿著人體血液方向的環(huán)境中均勻移動情形，基于能量提出了貪心能量感知和最優(yōu)能量感知兩個數(shù)據(jù)包轉(zhuǎn)發(fā)算法。貪心能量感知轉(zhuǎn)發(fā)算法，每次選擇當前具有最高能量的鄰居節(jié)點進行轉(zhuǎn)發(fā)，最終的能量消耗并不是最優(yōu)的；而最優(yōu)能量感知算法，從全局出發(fā)，每次選擇能夠最大化網(wǎng)絡能量的節(jié)點進行轉(zhuǎn)發(fā)，此算法需要全局信息。文獻[5]中基于層次分簇架構(gòu)提出了一個集中式路由框架。

綜上所述，無線傳感網(wǎng)中現(xiàn)有的非洪泛機制的數(shù)據(jù)包轉(zhuǎn)發(fā)方案沒有綜合考慮納米網(wǎng)中納米特性、分布性特性等。

2 算法

鑒于以上的分析和研究，在本文中我們提出了基于概率的洪泛算法PBF（Probabilistic Based Flooding），用于無線納米傳感網(wǎng)的廣播問題。PBF算法是一個分布式算法，每個節(jié)點獨立運行算法。每個節(jié)點發(fā)送數(shù)據(jù)包d有三種情形。情形一，若節(jié)點監(jiān)測的環(huán)境發(fā)生改變，自己產(chǎn)生數(shù)據(jù)包d需要發(fā)送出去，此時廣播的概率為1。然后存儲數(shù)據(jù)包d的ID號，對應flag標志置為true，目的是標記此節(jié)點已經(jīng)廣播過此數(shù)據(jù)包，下次再收到時降低概率發(fā)送。情形二，若節(jié)點收到數(shù)據(jù)包d并且對應flag標志為false,說明第一次收到數(shù)據(jù)包d，則以較高概率p1（屬于[0.6,1]）將此數(shù)據(jù)包廣播出去，若發(fā)送成功，對應flag標志置為true。情形三，若節(jié)點收到數(shù)據(jù)包d并且對應flag標志為true，說明以前此節(jié)點成功廣播過此消息，則以較低概率p2（屬于[0,0.6]）將此數(shù)據(jù)包廣播出去。納米節(jié)點的存儲能力有限，已發(fā)送數(shù)據(jù)包ID和對應flag標志的存儲按照最近最久未使用的算法進行淘汰。這里0.6的選取，只是使得p1為較高概率，p2為較低概率，并不影響算法的本質(zhì)。

下面給出基于概率的洪泛算法PBF：

算法. PBF

對于每個節(jié)點，

1： IF 節(jié)點u生成數(shù)據(jù)包d

2： 以概率1廣播，存儲d的ID，對應flag標志置為true

3： ENDIF

4： IF 節(jié)點u收到數(shù)據(jù)包d并且對應flag標志為false

5： 以概率p1（屬于[0.6,1]）發(fā)送，以概率1-p1不發(fā)送

6： IF 節(jié)點u發(fā)送數(shù)據(jù)包

7：d對應flag標志置為true

8： ENDIF

9： ENDIF

10：IF 節(jié)點u收到數(shù)據(jù)包d并且對應flag標志為true

11：以概率p2（屬于[0,0.6]）發(fā)送，以概率1-p2不發(fā)送

12：ENDIF

3 性能評估

本文采用Nano-Sim進行算法的仿真。NS3是一個開源的網(wǎng)絡仿真器，被廣泛采用。Nano-Sim是運行于NS3之上的模塊，可用于基于電磁的無線納米傳感網(wǎng)仿真。Nano-Sim是開源的、模塊化的、可擴展的。它的物理接口采用TS-OOK調(diào)制方案、簡單的MAC協(xié)議、一種基于洪泛技術(shù)的路由模塊以及用于生成和處理消息的單元。納米傳感器節(jié)點隨機分布在長方體區(qū)域。它們以20 cm/s的速度按選定方向隨機移動。納米接口部署于長方體中心，仿真期間位置固定不變。納米節(jié)點收集自己周圍環(huán)境信息，然后發(fā)送數(shù)據(jù)包給周圍節(jié)點。數(shù)據(jù)包從一個節(jié)點廣播到其它節(jié)點，直到納米接口。脈沖能量、脈沖持續(xù)時間和脈沖間隔時間等物理層參數(shù)根據(jù)Nano-Sim的原始工作設定[6]。為了考察PBF算法在無線納米傳感網(wǎng)中的性能，將它與一般的洪泛算法進行比較。每組仿真取30次運行結(jié)果的平均值。

為了考察PBF算法在無線納米傳感網(wǎng)中的性能，我們主要關(guān)注以下三個指標：數(shù)據(jù)包傳輸率PDR（Packet Delivery Ratio）、延遲和能量消耗。數(shù)據(jù)包傳輸率PDR是實際接收的數(shù)據(jù)包數(shù)量與需發(fā)送的數(shù)據(jù)包數(shù)量比率。延遲是數(shù)據(jù)包從源節(jié)點到目標節(jié)點傳輸所花費的時間。數(shù)據(jù)包若需要大量路由和重傳，會產(chǎn)生額外的能量消耗。接收的數(shù)據(jù)包數(shù)量和發(fā)送（包括轉(zhuǎn)發(fā)）的數(shù)據(jù)包數(shù)量的比率與成功接收每個數(shù)據(jù)包的所消耗能量是成正比的，而網(wǎng)絡中傳輸和接收數(shù)據(jù)包的總數(shù)量與此比率成正比。因此，能量消耗與網(wǎng)絡中傳輸和接收數(shù)據(jù)包的總數(shù)量正相關(guān)。眾所周知，能量消耗多，網(wǎng)絡的生存期就短。

圖1-圖3考察節(jié)點個數(shù)的不同（反映密度）對三個指標的影響，傳輸范圍取值為10 mm。圖1的垂直線表示平均延遲。為了獲得平均延遲，將所有傳送成功數(shù)據(jù)包延遲的總和除以傳送的數(shù)據(jù)包總數(shù)。結(jié)果表明，無論稠密網(wǎng)絡還是稀疏網(wǎng)絡中，洪泛算法和PBF算法性能接近，平均延遲大約75 ns。從圖2中觀察相同條件下兩個算法的數(shù)據(jù)包傳輸率，發(fā)現(xiàn)稀疏網(wǎng)絡中（節(jié)點個數(shù)從100～200）PBF算法此值低于100%，其余情況兩個算法的數(shù)據(jù)包傳輸率都為100%。稀疏網(wǎng)絡中PBF算法數(shù)據(jù)包傳輸率低，是因為數(shù)據(jù)包到達某節(jié)點，但因為按照一定概率轉(zhuǎn)發(fā)，碰巧沒有轉(zhuǎn)發(fā)出去，稀疏網(wǎng)絡中源節(jié)點和目標節(jié)點的通路本來就少，可能就沒有通路了，這樣此數(shù)據(jù)包就沒有到達目的節(jié)點。

圖1 傳感器數(shù)目與平均延遲

圖3給出了仿真時間內(nèi)網(wǎng)絡中所有節(jié)點傳輸和接收的數(shù)據(jù)包數(shù)量和，如果此值高，網(wǎng)絡中節(jié)點的能量消耗大。從圖中可以看到，PBF算法的發(fā)送和接收數(shù)據(jù)包總數(shù)要比洪泛算法低得多，也就是說使用此方案，有助于減少冗余廣播，可以大大減少無線納米傳感網(wǎng)中數(shù)據(jù)包傳輸和接收次數(shù)，從而節(jié)省能量，延長網(wǎng)絡使用壽命。我們的仿真沿用Nano-Sim的原始工作設定，沒有考慮節(jié)點之間相互的干擾。洪泛算法引起的廣播風暴問題，會造成大量重傳。因此，若考慮實際運行中相互間的干擾，洪泛算法會造成數(shù)據(jù)包的丟失，傳輸?shù)难舆t，特別是在稠密網(wǎng)絡中。若考慮干擾，稠密網(wǎng)絡時，洪泛算法在圖1中平均延遲可能增加，在圖2中數(shù)據(jù)包傳輸率可能到不了100%。

圖2 傳感器數(shù)目與數(shù)據(jù)包傳輸率

圖3 傳感器數(shù)目與發(fā)送和接收數(shù)據(jù)包總數(shù)

圖4 傳輸范圍與發(fā)送和平均延遲

圖5 傳輸范圍與數(shù)據(jù)包傳輸率

圖6 傳輸范圍與發(fā)送和接收數(shù)據(jù)包總數(shù)

圖4-圖6中，固定取節(jié)點個數(shù)為400，考察傳輸范圍對網(wǎng)絡行為的影響。圖4表明無論使用PBF算法還是洪泛算法，平均延遲的趨勢基本一致。傳輸范圍取值小，平均延遲小，原因是許多納米節(jié)點不連通，導致許多數(shù)據(jù)包無法到達目標節(jié)點，所以平均延遲小。當傳輸范圍為6 ns時，傳送成功的數(shù)據(jù)包多了，但傳輸范圍還不夠大，從源節(jié)點到目標節(jié)點所需要的跳數(shù)多，所以平均延遲最高。隨著傳輸范圍變大，從源節(jié)點到目標節(jié)點所需要的跳數(shù)減少，平均延遲又開始降低了。圖5中可見，兩個算法仿真時平均數(shù)據(jù)包傳輸率PDR變化規(guī)律很類似，當傳輸范圍為6 mm時，PDR達到或者接近100%。從圖6中可知，無論傳輸范圍為何值，PBF算法都能大大降低發(fā)送和接收數(shù)據(jù)包總數(shù)，也就是，大大減少了重復廣播。

4 結(jié) 語

本文設計了PBF算法，通過引入概率試圖減少數(shù)據(jù)包的重復轉(zhuǎn)發(fā)。仿真結(jié)果表明，PBF算法和傳統(tǒng)的洪泛算法平均延遲和數(shù)據(jù)傳輸率性能接近，而網(wǎng)絡中傳輸和接收數(shù)據(jù)包的總數(shù)量大大降低。也就是說，PBF算法能大大降低傳統(tǒng)的洪泛算法中數(shù)據(jù)包重復廣播的次數(shù)，因此能減少能量消耗，提高網(wǎng)絡生存期。下一步，我們會在Nano-Sim仿真中引入干擾模型，預計PBF算法在稠密網(wǎng)絡中平均延遲和數(shù)據(jù)傳輸率還會好于傳統(tǒng)洪泛算法，也會根據(jù)仿真情況進一步優(yōu)化PBF算法。