無線Ad Hoc網絡Steiner樹實現協議研究*

王 璐，李愛玲

(安陽工學院計算機科學與信息工程學院，河南安陽455000)

無線Ad hoc網絡是一種具有無中心、自組織、多跳路由、動態拓撲特點的特殊無線移動網絡。其出現是為了滿足跳出基礎設施支持的移動網絡，在其信號覆蓋范圍外仍可通訊，所以其需要多跳的通信方式。Ad hoc網絡中所有結點地位平等，無中心控制點，網絡結點可以通過自身的報文轉發功能向外傳遞數據信息，所以在功能上高于普通移動終端。當兩個移動終端的通訊范圍超出信號覆蓋范圍時，它們可以通過之間的其他終端分組轉發通信數據。由于每個移動終端通信覆蓋外圍的限制，Ad hoc網絡路由需要多個移動終端組成，數據信息需多次轉發才可到達目的終端［1］，這是Ad hoc網絡與其他移動網絡最根本區別，也是多跳特性的根本所在［2］。

無線Ad hoc網絡部署靈活、可靠性強、獲取信息精度高的特點使其在軍事偵察、交通運輸、環境監測方面應用前景廣闊。而由于其多跳的特性，拓撲結構隨時可能動態變化，網絡中有機協作各節點間的數據傳輸需要隨時考慮通信、能量、有限計算等問題［3］，由此Steiner樹的構造方法成為適應無線 Ad hoc網絡能源有限，生命周期短的最切合方案。

Steiner樹是總代價最小的分布樹［4］，其形狀隨組中成員關系的改變而改變，同時，它使連接特定圖中的特定組成員所需的鏈路數最少，這也是充分考慮到通信代價遠遠高于計算代價量級的原因［5］，盡量減少網絡中轉次數，利用數據聚合技術，減少數據傳輸所需要的中間環節以增強網絡的可靠性。另一方面，減少移動終端節點的使用量，也會減少產生擁塞的風險，使網絡相對更加穩定。但Steiner樹缺少通用的解決方案［6］，而本文利用協議聲明網絡為無線Ad Hoc網絡的最小Steiner樹問題提供了一種新的解決方案。

1 協議設計宣告方式

宣告性語言出現之前，宣告式方法首先在無線傳感器網絡中使用。程序通過其應用系統提供的編程接口，利用SQL語言從無線傳感器網絡中抽取數據，其過程類似于數據庫中數據的查詢。節點發現［7］、Oos 路經維護［8］、路由發現、拓撲發現［9］等很多問題都可用宣告式方法實現。而在推導式的數據庫查詢Datalog［10］基礎之上提出的描述路由協議的NDLog語言和和描述覆蓋層網絡協議的OverLog語言標志著宣告式網絡程序設計語言的實現。其后出現的Netlog語言，針對無線網絡環境中網絡節點移動性強引起的網絡節點失效、網絡動態性強的特點進行了挖掘，能夠更好的實現對網絡的動態性效果的有效支持。三者作為宣告式網絡程序設計語言的代表，均為推導式數據庫查詢語言Natalog的擴展，為網絡協議的設計者提供高層次的編程抽象。

協議的開發設計過程，是通過低層程序設計語言來直接控制網絡設備，往往涉及很多的技術細節，協議設計者往往不能將精力完全集中于協議本身的功能和特性上。宣告性語言相當于為網絡協議設計者提供了一個好的原型系統，使設計者只需關注協議行為，無需關心實現細節。在此基礎上開發出協議，在原型系統中試驗，利用試驗結果反饋來修改更進協議使其符合要求。其作用類似于網絡協議開發的中間件，編寫的網絡程序不需顧及低層具體的物理實現，只需要關心高層描述，完成其網絡行為需求即可，宣告性語言為網絡協議設計者擺脫各類異構設備物理層細節的束縛提供了可能。

相比而言，OverLog在NDLog的基礎上增加了網絡數據狀態(生存周期)的描述，可稱之為數據的軟狀態，利用它來刪除過期數據。若數據生存時間超過了其生存周期，那么將被刪除;若數據在超出其生存周期前被節點重新利用，它的生存周期將被重置;這針對生活中的動態網絡無疑是一大進步。然而無論是NDLog還是OverLog，都是需要啟發式定義的，此方面Netlog更勝一籌，語言的定義實現了形式化，經過了充分的語法語義討論，而且Netlog主要針對無線網絡設計，特別是無線Ad Hoc網絡，無線網絡協議編程提供了強有力的工具。本文的協議實現也在Netlog語言基礎之上。

2 算法描述

求最小 Steiner樹是非常困難的，它屬于 NP Complete問題［11］。但最小Steiner樹具有重要的應用價值，它在交通運輸的規劃、輸油管道和航空港的安排、通訊線路的布置和計算機的設計等等現代經濟與科技、軍事領域中的廣泛應用［12］。本文聲明最小Steiner樹協議也是用來快速構造一棵近似最小的Steiner樹。

針對網絡中的各通信節點，我們通常會選定合適的節點使目的節點間的通信代價最小。其網絡模型可對應成給定的網絡無向連通圖G，把權值作為節點傳輸的代價，那么生成樹各邊的權值總和即樹的權最小的生成樹，即為圖G的最小生成樹MST(Minimal Spanning Tree)，也即該網絡最小代價的生成樹。

設圖G={V，E，C}，V為節點的非空有限集合E是V中可以直接通信的節點對集合，C是節點對間傳輸代價的集合，其中V，E均非空。節點集合V非空子集S被稱為G的Steiner節點集合。對于給定網絡的連通圖G和Steiner節點集合S，T是G和S上的Steiner樹，當且僅當S中的所有節點都在T上。G和S上的最小Steiner樹是在所有Steiner樹中各邊的權值總和最小的樹。

構造虛擬全聯通網絡G'={S，E，C}，對于S中任意兩點，它們在G'中的傳輸代價是G中兩點間的最小代價路徑的代價和。

構造G'上的最小生成樹T'。

將T'中的邊對應的G中的路徑上的所有邊，標記為2。由標記為2的邊及其對應定點組成的圖記為G″。

構造G″上的最小生成樹T″。

將T″葉子節點中的非Steiner節點移除。

每個節點獨立運行聲明Steiner樹協議，構造Steiner節點間的虛擬全聯通網絡，在此網絡上構造最小代價生成樹;然后將此樹的節點與邊對應原網絡的節點和邊，繼續構造最小代價生成樹，將此樹上的非Steiner節點的葉子節點刪除，就近似得到了最小代價Steiner樹。

由于協議代碼較為復雜，現僅以權值更新部分協議代碼為例解釋，其有18條協議規定構成:

規定主要針對各節點的相鄰節點列表和虛擬節點列表執行權值及序號的修改:

(1)權值為0的節點優先于權值為1的節點鏈接。

(2)無權值為0節點時，權值為1的節點優先級上升，并設為默認權值。

(3)針對用于鏈接的廣播消息，接收點遍歷其鄰節點列表，權值為0的修改為2。

(4)針對用于鏈接的廣播消息，遍歷其接收點的下一個接收點狀態，權值為0或者大于廣播消息中給定權值時，將其權值也設定為2.

(5)表內權值與鏈接廣播消息內權值相等時廣播點ID小于本地ID地址，且下一鏈接點表內狀態為0，也將其權值設定為2。

(6)廣播點ID大于本地ID地址時，消息繼續轉發給狀態為1的節點。

(7)若廣播點為新節點，無序列號，廣播消息直接轉發給狀態為1的鄰節點。將廣播消息內序列號指定為其序列號插入節點序列列表。

(8)廣播消息內序號若大于原表內序號，則表內序號替換為廣播消息序號。

3 仿真模擬

聲明Steiner樹協議是在網絡上分布式構造近似最小Steiner樹。此處使用WSNS(Wireless Net work Event-Driven Simulator)［13］作為模擬實驗平臺該實驗平臺具有精確的節點內部結構模擬和無線媒介模擬功能。隨機在360×360的平面內分布15個節點，節點的通訊半徑設為80。當兩節點在通訊范圍之內，則隨機為其分配一個鏈接代價，同一鏈接的兩個節點間鏈接代價相同。初始網絡如圖1所示。網絡中每個節點獨立運行聲明Steiner樹協議，Steiner節點去構造Steiner節點間的虛擬全聯通網絡，在此網絡上構造最小代價生成樹;然后將此樹的節點與邊對應原網絡的節點和邊，繼續構造最小代價生成樹，將此樹上的非Steiner節點的葉子節點刪除，就近似得到了最小代價Steiner樹，如圖2所示。實驗結果顯示，聲明Steiner協議能夠快速構造一棵近似最小Steiner樹。

圖1 初始網絡

圖2 仿真平臺實現構造近似Steiner樹

4 小結

實驗結果表明，本方法是可以快速的構造一棵近似最小Steiner樹的。此原型系統符合網絡協議設計需求，使得設計者可以忽略底層技術細節僅關注協議行為。同時也為無線移動網絡中資源的選擇利用提供了一種新的可嘗試性的方法。

［1］王慶文，史浩山，程偉，等.一種基于跨層設計的Ad hoc網絡按需路由協議［J］.傳感技術學報，2009，22(12):1780-1783.

［2］譚學治，吳少川，賈世樓.移動Ad hoc網絡分布式多跳認證授權方案［J］.電子器件，2005，28(3):672-677.

［3］李宏，于宏毅，劉婀娜.一種基于樹的無線傳感器網絡數據收集方法［J］.電子與信息學報，2007，29(7):1633-1637.

［4］王建平，賈東耀，周賢偉.基于虛擬Steiner樹的無線傳感器網絡組播隨機路由協議研究［J］.傳感技術學報，2008，21(11)1896-1899.

［5］Pottie G，Kaiser W.Wireless Sensor Networks［J］.Communications of the ACM，2000，5，43(5):51-58.

［6］閆中江，沈中，常義林，等.一種修復網絡拓撲的Steiner樹移動控制算法［J］.西安交通大學學報，2011，45(2):39-43.

［7］Alonso G，Kranakis E，Sawchuk C，et al.Probabilistic Protocols for Node Discovery in Ad Hoe Multi-Channel Broadcast Networks［C］//ADHOC-Now.2003:104-115.

［8］Bejerano Y，Breitbart Y，Orda A，et al.Algorithms for Computing QoS Paths with Restoration［J］.IEEE/ACM Trans.Netw，2005，13(3):648-661.

［9］Bejerano Y，Breitbart Y，Garofalakis M，et al.Physical Topology Discovery for Large Multi-Subnet Networks［C］∥Proc.IEEE Info com.2003:342-352.

［10］Ramakrishnan R，Ullman J D.A Survey of Deductive Database Sys tems［J］.J.Log.Program，1995，23(2):125-149.

［11］丁雪楓，馬良，丁雪松.基于模擬植物生長算法的構造通訊網絡Steiner最優樹方法［J］.上海理工大學學報，2010，32(1):88-91.

［12］范容，潘雪增，傅建慶，等.基于Steiner樹的層次型無線傳感器網絡安全組播協議［J］.傳感技術學報，2011，24(4):601-608.

［13］Guillaume Chelius.Worldsens:A Fast and Accurate Developmen Framework for Sensor Network Applications［EB/OL］.http://ws net.gfo-ge.inria.fr/.