無線Ad Hoc網(wǎng)絡(luò)Steiner樹實(shí)現(xiàn)協(xié)議研究*

王 璐，李愛玲

(安陽工學(xué)院計(jì)算機(jī)科學(xué)與信息工程學(xué)院，河南安陽455000)

無線Ad hoc網(wǎng)絡(luò)是一種具有無中心、自組織、多跳路由、動態(tài)拓?fù)涮攸c(diǎn)的特殊無線移動網(wǎng)絡(luò)。其出現(xiàn)是為了滿足跳出基礎(chǔ)設(shè)施支持的移動網(wǎng)絡(luò)，在其信號覆蓋范圍外仍可通訊，所以其需要多跳的通信方式。Ad hoc網(wǎng)絡(luò)中所有結(jié)點(diǎn)地位平等，無中心控制點(diǎn)，網(wǎng)絡(luò)結(jié)點(diǎn)可以通過自身的報文轉(zhuǎn)發(fā)功能向外傳遞數(shù)據(jù)信息，所以在功能上高于普通移動終端。當(dāng)兩個移動終端的通訊范圍超出信號覆蓋范圍時，它們可以通過之間的其他終端分組轉(zhuǎn)發(fā)通信數(shù)據(jù)。由于每個移動終端通信覆蓋外圍的限制，Ad hoc網(wǎng)絡(luò)路由需要多個移動終端組成，數(shù)據(jù)信息需多次轉(zhuǎn)發(fā)才可到達(dá)目的終端［1］，這是Ad hoc網(wǎng)絡(luò)與其他移動網(wǎng)絡(luò)最根本區(qū)別，也是多跳特性的根本所在［2］。

無線Ad hoc網(wǎng)絡(luò)部署靈活、可靠性強(qiáng)、獲取信息精度高的特點(diǎn)使其在軍事偵察、交通運(yùn)輸、環(huán)境監(jiān)測方面應(yīng)用前景廣闊。而由于其多跳的特性，拓?fù)浣Y(jié)構(gòu)隨時可能動態(tài)變化，網(wǎng)絡(luò)中有機(jī)協(xié)作各節(jié)點(diǎn)間的數(shù)據(jù)傳輸需要隨時考慮通信、能量、有限計(jì)算等問題［3］，由此Steiner樹的構(gòu)造方法成為適應(yīng)無線 Ad hoc網(wǎng)絡(luò)能源有限，生命周期短的最切合方案。

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

1 協(xié)議設(shè)計(jì)宣告方式

宣告性語言出現(xiàn)之前，宣告式方法首先在無線傳感器網(wǎng)絡(luò)中使用。程序通過其應(yīng)用系統(tǒng)提供的編程接口，利用SQL語言從無線傳感器網(wǎng)絡(luò)中抽取數(shù)據(jù)，其過程類似于數(shù)據(jù)庫中數(shù)據(jù)的查詢。節(jié)點(diǎn)發(fā)現(xiàn)［7］、Oos 路經(jīng)維護(hù)［8］、路由發(fā)現(xiàn)、拓?fù)浒l(fā)現(xiàn)［9］等很多問題都可用宣告式方法實(shí)現(xiàn)。而在推導(dǎo)式的數(shù)據(jù)庫查詢Datalog［10］基礎(chǔ)之上提出的描述路由協(xié)議的NDLog語言和和描述覆蓋層網(wǎng)絡(luò)協(xié)議的OverLog語言標(biāo)志著宣告式網(wǎng)絡(luò)程序設(shè)計(jì)語言的實(shí)現(xiàn)。其后出現(xiàn)的Netlog語言，針對無線網(wǎng)絡(luò)環(huán)境中網(wǎng)絡(luò)節(jié)點(diǎn)移動性強(qiáng)引起的網(wǎng)絡(luò)節(jié)點(diǎn)失效、網(wǎng)絡(luò)動態(tài)性強(qiáng)的特點(diǎn)進(jìn)行了挖掘，能夠更好的實(shí)現(xiàn)對網(wǎng)絡(luò)的動態(tài)性效果的有效支持。三者作為宣告式網(wǎng)絡(luò)程序設(shè)計(jì)語言的代表，均為推導(dǎo)式數(shù)據(jù)庫查詢語言Natalog的擴(kuò)展，為網(wǎng)絡(luò)協(xié)議的設(shè)計(jì)者提供高層次的編程抽象。

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

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

2 算法描述

求最小 Steiner樹是非常困難的，它屬于 NP Complete問題［11］。但最小Steiner樹具有重要的應(yīng)用價值，它在交通運(yùn)輸?shù)囊?guī)劃、輸油管道和航空港的安排、通訊線路的布置和計(jì)算機(jī)的設(shè)計(jì)等等現(xiàn)代經(jīng)濟(jì)與科技、軍事領(lǐng)域中的廣泛應(yīng)用［12］。本文聲明最小Steiner樹協(xié)議也是用來快速構(gòu)造一棵近似最小的Steiner樹。

針對網(wǎng)絡(luò)中的各通信節(jié)點(diǎn)，我們通常會選定合適的節(jié)點(diǎn)使目的節(jié)點(diǎn)間的通信代價最小。其網(wǎng)絡(luò)模型可對應(yīng)成給定的網(wǎng)絡(luò)無向連通圖G，把權(quán)值作為節(jié)點(diǎn)傳輸?shù)拇鷥r，那么生成樹各邊的權(quán)值總和即樹的權(quán)最小的生成樹，即為圖G的最小生成樹MST(Minimal Spanning Tree)，也即該網(wǎng)絡(luò)最小代價的生成樹。

設(shè)圖G={V，E，C}，V為節(jié)點(diǎn)的非空有限集合E是V中可以直接通信的節(jié)點(diǎn)對集合，C是節(jié)點(diǎn)對間傳輸代價的集合，其中V，E均非空。節(jié)點(diǎn)集合V非空子集S被稱為G的Steiner節(jié)點(diǎn)集合。對于給定網(wǎng)絡(luò)的連通圖G和Steiner節(jié)點(diǎn)集合S，T是G和S上的Steiner樹，當(dāng)且僅當(dāng)S中的所有節(jié)點(diǎn)都在T上。G和S上的最小Steiner樹是在所有Steiner樹中各邊的權(quán)值總和最小的樹。

構(gòu)造虛擬全聯(lián)通網(wǎng)絡(luò)G'={S，E，C}，對于S中任意兩點(diǎn)，它們在G'中的傳輸代價是G中兩點(diǎn)間的最小代價路徑的代價和。

構(gòu)造G'上的最小生成樹T'。

將T'中的邊對應(yīng)的G中的路徑上的所有邊，標(biāo)記為2。由標(biāo)記為2的邊及其對應(yīng)定點(diǎn)組成的圖記為G″。

構(gòu)造G″上的最小生成樹T″。

將T″葉子節(jié)點(diǎn)中的非Steiner節(jié)點(diǎn)移除。

每個節(jié)點(diǎn)獨(dú)立運(yùn)行聲明Steiner樹協(xié)議，構(gòu)造Steiner節(jié)點(diǎn)間的虛擬全聯(lián)通網(wǎng)絡(luò)，在此網(wǎng)絡(luò)上構(gòu)造最小代價生成樹;然后將此樹的節(jié)點(diǎn)與邊對應(yīng)原網(wǎng)絡(luò)的節(jié)點(diǎn)和邊，繼續(xù)構(gòu)造最小代價生成樹，將此樹上的非Steiner節(jié)點(diǎn)的葉子節(jié)點(diǎn)刪除，就近似得到了最小代價Steiner樹。

由于協(xié)議代碼較為復(fù)雜，現(xiàn)僅以權(quán)值更新部分協(xié)議代碼為例解釋，其有18條協(xié)議規(guī)定構(gòu)成:

規(guī)定主要針對各節(jié)點(diǎn)的相鄰節(jié)點(diǎn)列表和虛擬節(jié)點(diǎn)列表執(zhí)行權(quán)值及序號的修改:

(1)權(quán)值為0的節(jié)點(diǎn)優(yōu)先于權(quán)值為1的節(jié)點(diǎn)鏈接。

(2)無權(quán)值為0節(jié)點(diǎn)時，權(quán)值為1的節(jié)點(diǎn)優(yōu)先級上升，并設(shè)為默認(rèn)權(quán)值。

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

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

(5)表內(nèi)權(quán)值與鏈接廣播消息內(nèi)權(quán)值相等時廣播點(diǎn)ID小于本地ID地址，且下一鏈接點(diǎn)表內(nèi)狀態(tài)為0，也將其權(quán)值設(shè)定為2。

(6)廣播點(diǎn)ID大于本地ID地址時，消息繼續(xù)轉(zhuǎn)發(fā)給狀態(tài)為1的節(jié)點(diǎn)。

(7)若廣播點(diǎn)為新節(jié)點(diǎn)，無序列號，廣播消息直接轉(zhuǎn)發(fā)給狀態(tài)為1的鄰節(jié)點(diǎn)。將廣播消息內(nèi)序列號指定為其序列號插入節(jié)點(diǎn)序列列表。

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

3 仿真模擬

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

圖1 初始網(wǎng)絡(luò)

圖2 仿真平臺實(shí)現(xiàn)構(gòu)造近似Steiner樹

4 小結(jié)

實(shí)驗(yàn)結(jié)果表明，本方法是可以快速的構(gòu)造一棵近似最小Steiner樹的。此原型系統(tǒng)符合網(wǎng)絡(luò)協(xié)議設(shè)計(jì)需求，使得設(shè)計(jì)者可以忽略底層技術(shù)細(xì)節(jié)僅關(guān)注協(xié)議行為。同時也為無線移動網(wǎng)絡(luò)中資源的選擇利用提供了一種新的可嘗試性的方法。

［1］王慶文，史浩山，程偉，等.一種基于跨層設(shè)計(jì)的Ad hoc網(wǎng)絡(luò)按需路由協(xié)議［J］.傳感技術(shù)學(xué)報，2009，22(12):1780-1783.

［2］譚學(xué)治，吳少川，賈世樓.移動Ad hoc網(wǎng)絡(luò)分布式多跳認(rèn)證授權(quán)方案［J］.電子器件，2005，28(3):672-677.

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

［4］王建平，賈東耀，周賢偉.基于虛擬Steiner樹的無線傳感器網(wǎng)絡(luò)組播隨機(jī)路由協(xié)議研究［J］.傳感技術(shù)學(xué)報，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］閆中江，沈中，常義林，等.一種修復(fù)網(wǎng)絡(luò)拓?fù)涞腟teiner樹移動控制算法［J］.西安交通大學(xué)學(xué)報，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］丁雪楓，馬良，丁雪松.基于模擬植物生長算法的構(gòu)造通訊網(wǎng)絡(luò)Steiner最優(yōu)樹方法［J］.上海理工大學(xué)學(xué)報，2010，32(1):88-91.

［12］范容，潘雪增，傅建慶，等.基于Steiner樹的層次型無線傳感器網(wǎng)絡(luò)安全組播協(xié)議［J］.傳感技術(shù)學(xué)報，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/.