無線納米傳感網中基于概率的洪泛算法*

夏建川，張秀娟，王斯鋒

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

0 引 言

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

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

本文第2節列出相關工作；第3節給出能減少冗余傳輸的詳細算法；第4節是仿真結果及性能分析，并指出下一步工作方向。

1 相關工作

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

綜上所述，無線傳感網中現有的非洪泛機制的數據包轉發方案沒有綜合考慮納米網中納米特性、分布性特性等。

2 算法

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

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

算法. PBF

對于每個節點，

1： IF 節點u生成數據包d

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

3： ENDIF

4： IF 節點u收到數據包d并且對應flag標志為false

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

6： IF 節點u發送數據包

7：d對應flag標志置為true

8： ENDIF

9： ENDIF

10：IF 節點u收到數據包d并且對應flag標志為true

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

12：ENDIF

3 性能評估

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

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

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

圖1 傳感器數目與平均延遲

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

圖2 傳感器數目與數據包傳輸率

圖3 傳感器數目與發送和接收數據包總數

圖4 傳輸范圍與發送和平均延遲

圖5 傳輸范圍與數據包傳輸率

圖6 傳輸范圍與發送和接收數據包總數

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

4 結 語

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