基于移動代理的無線自組網(wǎng)絡拓撲發(fā)現(xiàn)算法研究

摘 要：隨著當代無線網(wǎng)絡的迅猛發(fā)展，無線自組網(wǎng)絡應運而生，而網(wǎng)絡拓撲發(fā)現(xiàn)技術(shù)作為網(wǎng)絡管理的核心，在網(wǎng)絡運行中起著至關重要的作用，因而對無線自組網(wǎng)絡拓撲發(fā)現(xiàn)的研究也逐漸成為了熱點。在深入研究傳統(tǒng)的基于移動代理的拓撲發(fā)現(xiàn)算法之后，給出一種改進的新思想，采用劃分子網(wǎng)的方法，該方法可以在提高拓撲發(fā)現(xiàn)的基礎上有效地減少網(wǎng)絡負載，并且能夠降低網(wǎng)絡帶寬，在一定程度上改善了網(wǎng)絡拓撲收斂速度過慢的缺點。

關鍵詞：無線自組網(wǎng)絡； 拓撲發(fā)現(xiàn)； 移動代理； 劃分子網(wǎng)

中圖分類號： TN915?34 文獻標識碼： A 文章編號： 1004?373X（2016）18?0039?04

Abstract： With the rapid development of modern wireless network， the wireless Ad hoc network arises at the right moment. The network topology discovery technology as the core of network management plays an important role in network operation. Therefore， research of the wireless Ad hoc network topology discovery has gradually become a hot spot. An improved new idea， that is， the method of subnet division is presented based on study of the traditional topology discovery algorithm based on mobile agent. It can effectively reduce the network load on the premise of improving the topology discovery， reduce the network bandwidth， and overcome the disadvantage that convergence rate of the network topology is slow to a certain extent.

Keywords： wireless Ad hoc network； topology discovery； mobile agent； subnet division

0 引 言

移動自組網(wǎng)（MANET）是由一組帶有無線收發(fā)裝置的移動終端組成的一個多跳的臨時性自治系統(tǒng)，它的每個節(jié)點在網(wǎng)絡中隨機的移動，通過無線連接組成任意的網(wǎng)絡拓撲結(jié)構(gòu)，它具有分布性和移動性等特性。

移動代理起源于人工智能，早在20世紀80年代的中期，人工智能技術(shù)結(jié)合了分布式計算技術(shù)，進而產(chǎn)生了分布式人工智能方向。移動代理在復雜的網(wǎng)絡系統(tǒng)中能自主地從一臺主機移動到另一臺主機，并且可以選擇何時、向何方向移動，在移動中移動代理可以根據(jù)要求掛起其運行，然后轉(zhuǎn)到網(wǎng)絡的其他地方重新開始或繼續(xù)其執(zhí)行。移動代理的兩大特性是移動性（mobility）和自治性（autonomy），因此移動代理與移動自組網(wǎng)具有天然的共性它憑借自身的特性與優(yōu)勢打破了人工智能領域停滯不前的僵局，進而被人們廣泛的接受，也使得它有了新的發(fā)展空間。MIT媒體實驗室很早就提出了使用移動代理來研究拓撲發(fā)現(xiàn)的思想[1]。通過移動代理來為網(wǎng)絡中的每個節(jié)點收集相關的拓撲信息，并且可以轉(zhuǎn)發(fā)給其他相鄰節(jié)點，最終達到使所有節(jié)點都能夠獲得全網(wǎng)拓撲信息的目的。同時，移動代理還有定期更新拓撲信息的功能。

1 無線自組網(wǎng)絡拓撲發(fā)現(xiàn)的常用方法

傳統(tǒng)的無線自組網(wǎng)絡拓撲發(fā)現(xiàn)，通常是利用節(jié)點間無線通信的廣播機制來獲得該節(jié)點的鄰居節(jié)點的信息，并且運用拓撲發(fā)現(xiàn)分組的擴散來產(chǎn)生拓撲結(jié)構(gòu)，每個節(jié)點將所獲得的拓撲信息傳遞給它的下一跳節(jié)點，從而形成完整的網(wǎng)絡拓撲。當前無線自組網(wǎng)絡拓撲發(fā)現(xiàn)技術(shù)層出不窮，最常見的方法有以下幾種：

（1） 基于ICMP的方法。此方法能夠較高效地發(fā)現(xiàn)網(wǎng)絡設備，但由于它主要利用ping操作，只能確定從管理站到目的IP是否可達，中間過程沒有具體的信息獲得，比如經(jīng)過哪些路由器等，所以要想分析它們的連接關系是比較復雜的，此外各個IP所在子網(wǎng)情況也難以判斷。并且，它需要對IP地址進行ping和traceroute操作，而它所利用的traceroute工具屬于主動性較強的工具，無形中增加了網(wǎng)絡負擔。所以相比而言，它們還是比較適合子網(wǎng)內(nèi)主機的發(fā)現(xiàn)。

（2） 基于ARP的方法。ARP表中的網(wǎng)絡設備地址都是最近活動過的有效IP地址，幾乎沒有冗余信息，拓撲發(fā)現(xiàn)效率高、開銷低，但由于ARP協(xié)議本身的局限性使得節(jié)點的發(fā)現(xiàn)范圍小，比較適合應用于局域網(wǎng)中[2]。

（3） 基于SNMP的方法。此方法通過獲取MIB中的信息來得到網(wǎng)絡拓撲圖。它的發(fā)現(xiàn)過程和算法簡單，發(fā)現(xiàn)效率較高，并且系統(tǒng)和網(wǎng)絡的開銷小，易于實現(xiàn)。但是該方法無法發(fā)現(xiàn)網(wǎng)絡中不支持SNMP協(xié)議或沒有安裝SNMP代理的網(wǎng)絡設備，而且路由表中包含了大量的冗余信息。

（4） 基于OSPF的方法。該發(fā)現(xiàn)方法只需要訪問區(qū)域邊界路由器，顯然效率和速度都有了較大提高，但該方法也存在一些不足：首先，它要求網(wǎng)絡設備都支持OSPF協(xié)議；其次，由于OSPF涉及路由部分的算法相對來講比較復雜，所以實現(xiàn)起來難度較大；最后，由于利用ping來發(fā)現(xiàn)活動的主機，所以速度較慢。

本文詳細分析了傳統(tǒng)的無線自組網(wǎng)絡拓撲發(fā)現(xiàn)算法，在對基于移動代理的拓撲發(fā)現(xiàn)算法深入研究之后，進行了算法的改進，改進的算法能夠在一定程度上減輕網(wǎng)絡負載，提高網(wǎng)絡收斂速度。

2 現(xiàn)有的無線自組網(wǎng)絡拓撲發(fā)現(xiàn)算法

在文獻[3?4]中，Marwaha等人提出Ant?AODV算法，該算法使用類似移動代理的螞蟻，主要針對AODV路由協(xié)議的分布式拓撲發(fā)現(xiàn)；由于該算法中螞蟻任意移動，導致螞蟻的歷史記錄較大，增大了負載。

在文獻[5]中，Aissani等人提出Ant?DSR算法，優(yōu)點是利用螞蟻代理進行路由發(fā)現(xiàn)，網(wǎng)絡負載較小，缺點是當網(wǎng)絡低移動或低負載時，Ant?DSR算法對網(wǎng)絡性能并沒有特別優(yōu)化，而且螞蟻代理的引入還增加了網(wǎng)絡負載。在文獻[6?7]中，Choudhury等人提出了一種分布式拓撲發(fā)現(xiàn)機制，使用基于類移動代理的螞蟻來進行無線自組網(wǎng)絡拓撲發(fā)現(xiàn)；該算法采用了多代理技術(shù)進行無線自組網(wǎng)絡拓撲發(fā)現(xiàn)，缺點是缺乏適當?shù)倪w移策略，多個螞蟻在網(wǎng)絡中無目的遷移，導致網(wǎng)絡連通度高的地方螞蟻數(shù)量較多，網(wǎng)絡負載較大。

在文獻[8]中，加拿大University of Calgary的研究小組提出了他們的M?S移動代理的拓撲發(fā)現(xiàn)框架；他們把移動代理分為了兩種，即Manager代理和Service代理，分別屬于群首和群內(nèi)成員；“Ant”Based系統(tǒng)是純粹基于先驗式的，現(xiàn)在大多數(shù)的基于移動代理的拓撲發(fā)現(xiàn)都是“Ant”Based，他們存在一些缺點，比如代理丟失，帶寬的不必要消耗，以及對網(wǎng)絡的適應性不強。

本文提出的拓撲發(fā)現(xiàn)算法采用劃分子網(wǎng)的方法來限制移動代理的任意移動，移動代理只能在自己的子網(wǎng)中移動，從而減少了歷史記錄，能夠在一定程度上減輕網(wǎng)絡負載，提高了網(wǎng)絡的收斂速度，并且與引入的駐留代理相結(jié)合，改變了移動代理的丟失和節(jié)點拓撲信息的丟失現(xiàn)象。最后又引入了移動總代理，使網(wǎng)管節(jié)點可以通過產(chǎn)生的移動總代理來收集所有移動代理攜帶的節(jié)點拓撲信息，該方法能夠防止收集信息時移動代理的洪泛，在一定程度上減少了帶寬的消耗。

3 改進的基于移動代理的拓撲發(fā)現(xiàn)算法

3.1 算法理論依據(jù)

3.1.1 信息素濃度

設集合S表示網(wǎng)絡中的全部節(jié)點，集合Na表示節(jié)點a的所有鄰居節(jié)點，節(jié)點b位于節(jié)點a的鄰居鏈路中。信息素濃度Tab（t）表示在t時刻，節(jié)點a（a∈S）選擇以節(jié)點b（b∈Na）作為下一跳時，由節(jié)點a和節(jié)點b所組成的鏈路Lab的信息素濃度值，并且其值要大于等于零，即Tab（t）≥0。

3.2 算法描述

在無線自組網(wǎng)絡拓撲發(fā)現(xiàn)算法中，通常采用基于移動代理的拓撲發(fā)現(xiàn)方式。這種方式解決了主動式路由策略和基于需求路由策略的不足[9]。本文在基于移動代理的基礎上，選取網(wǎng)管節(jié)點，引入駐留移動代理并將網(wǎng)絡按照一定規(guī)則劃分成若干的子網(wǎng)，使節(jié)點只能在各自的子網(wǎng)內(nèi)遷移，并且引入了移動總代理，網(wǎng)管節(jié)點可以通過產(chǎn)生的移動總代理來收集所有移動代理攜帶的節(jié)點拓撲信息。這種結(jié)合方式能夠在提高拓撲發(fā)現(xiàn)的基礎上有效減少網(wǎng)絡負載，防止在遷移過程中因節(jié)點丟失而引起的移動代理丟失以及移動代理所攜帶拓撲信息的丟失，從而更準確快速，有效地獲得全網(wǎng)的拓撲信息。

根據(jù)無線自組網(wǎng)絡的特點，并對傳統(tǒng)的算法進行了分析總結(jié)之后，提出以下算法：

根據(jù)地理位置，將整個網(wǎng)絡劃分成幾個子網(wǎng)絡，一定程度上起到限制網(wǎng)絡中移動代理洪泛的作用。并在每個子網(wǎng)中設立一個網(wǎng)管節(jié)點，其他節(jié)點作為該子網(wǎng)的成員節(jié)點。網(wǎng)管節(jié)點作為每個子網(wǎng)的管理員，它是在計算了電池能量、處理器能量以及信號強度的大小之后做出選擇的。它通常也與網(wǎng)絡中的位置有關，常會考慮選擇網(wǎng)絡中位置處于最中央的設備作為網(wǎng)管節(jié)點，這樣它能更好地與其他子網(wǎng)的網(wǎng)管節(jié)點進行信息交換，且開銷較小，耗時較短。

網(wǎng)絡開始時，由每個子網(wǎng)中的網(wǎng)管節(jié)點發(fā)送消息，同一子網(wǎng)內(nèi)的成員節(jié)點都能接收到該消息。在網(wǎng)絡中仍然保留傳統(tǒng)的移動代理，并在所有的網(wǎng)管節(jié)點和成員節(jié)點中各保存一個駐留代理，每個子網(wǎng)的網(wǎng)管節(jié)點產(chǎn)生一個移動總代理，用來收集所有移動代理攜帶的成員節(jié)點的拓撲信息，在一定程度上能夠減少移動代理返回信息時而引起的移動代理洪泛的現(xiàn)象，減輕網(wǎng)絡負載。由于大量實驗表明，最佳移動代理數(shù)目應為網(wǎng)絡中所有節(jié)點數(shù)目的一半，所以移動代理的初值暫且保留節(jié)點數(shù)目的一半即可。節(jié)點在開始運行時會產(chǎn)生一個隨機數(shù)，如果此數(shù)為奇數(shù)，則產(chǎn)生移動代理，此數(shù)為偶數(shù)則不產(chǎn)生移動代理，這樣就能保證產(chǎn)生的移動代理數(shù)目為節(jié)點數(shù)目的一半。每個子網(wǎng)中的移動代理只能在本子網(wǎng)內(nèi)任意移動，且不斷地收集該子網(wǎng)內(nèi)所有節(jié)點的拓撲信息，并進行定期的分發(fā)和更新。

為了避免因節(jié)點和移動代理的任意移動而丟失拓撲信息，導致網(wǎng)絡拓撲頻繁發(fā)生變化；每個節(jié)點的信息不僅保存在該節(jié)點中，也會復制一份在該節(jié)點的駐留代理中。駐留代理和節(jié)點同時產(chǎn)生，同時消亡，有效減少了網(wǎng)絡負載。

移動代理不斷地從其所在子網(wǎng)中的某個節(jié)點遷移到該節(jié)點的某一鄰居節(jié)點。在此之前，該節(jié)點會根據(jù)式（3）計算出當前時刻該節(jié)點的每一條鄰居鏈路的信息素濃度值。網(wǎng)絡中每個節(jié)點都會保存一個本地鄰居鏈路的信息素濃度表，鄰居鏈路信息素濃度表中記錄了某節(jié)點以其任意鄰居節(jié)點為遷移節(jié)點時，該條鄰居鏈路的信息素濃度值，其值與移動代理的遷移概率成反比，由式（5）可知，如果一條鏈路被移動代理選擇過，其鏈路信息素濃度會增高；反之，如果一條鏈路很少有移動代理經(jīng)過，其鏈路信息素濃度會降低，移動代理會根據(jù)此記錄來選擇遷移方向。

在遷移過程中，移動代理不斷地收集其子網(wǎng)內(nèi)所有節(jié)點的拓撲信息。如果遇到其他移動代理，則可以相互交換彼此未到達的節(jié)點的拓撲信息。如果有兩個移動代理同時到達某個節(jié)點，則根據(jù)兩個移動代理中記錄的計數(shù)器值來判斷哪個移動代理比較新，進而選用比較新的移動代理所攜帶的拓撲信息。

如果有新節(jié)點加入子網(wǎng)，則由舊節(jié)點復制一份該子網(wǎng)的拓撲信息給新加入的節(jié)點，然后重新選擇該子網(wǎng)的網(wǎng)管節(jié)點，并且移動代理與成員節(jié)點之間互相更新拓撲信息，刪除過時的拓撲信息，添加新的拓撲信息。最后將更新的拓撲信息表存于每個成員節(jié)點中，再復制一份存于該節(jié)點的駐留代理中。在移動代理離開時，節(jié)點及移動代理都將各自的計數(shù)器值加1，為移動代理所攜帶拓撲信息的新舊程度的辨別提供了方便。最后，網(wǎng)管節(jié)點發(fā)出一個移動總代理來收集該子網(wǎng)中所有移動代理攜帶的成員節(jié)點拓撲信息，進行整合后把新的拓撲信息表返回給網(wǎng)管節(jié)點，并且復制一份發(fā)送給網(wǎng)管節(jié)點的駐留代理。每個子網(wǎng)內(nèi)的拓撲發(fā)現(xiàn)都是通過移動代理來實現(xiàn)的。

網(wǎng)管節(jié)點周期性地發(fā)送消息給本子網(wǎng)的成員節(jié)點，并等待回應。如果某成員節(jié)點在設定的時間內(nèi)沒有回應，說明該節(jié)點已經(jīng)不在本子網(wǎng)內(nèi)，移動代理則刪除該節(jié)點并更新該子網(wǎng)的拓撲信息，并將新的拓撲信息返回給該子網(wǎng)的網(wǎng)管節(jié)點。網(wǎng)管節(jié)點之間也周期性地交換各自子網(wǎng)的拓撲信息，從而達到更新整個網(wǎng)絡拓撲的目的。

3.3 算法流程圖

算法流程圖如圖2所示。

4 結(jié) 語

拓撲發(fā)現(xiàn)是網(wǎng)絡管理的核心，而基于移動代理的拓撲發(fā)現(xiàn)又是無線自組網(wǎng)的一個重要研究領域。本文采用網(wǎng)絡劃分子網(wǎng)的方法，在每個子網(wǎng)中選擇一個網(wǎng)管節(jié)點，再引入駐留代理，并且保留一半節(jié)點數(shù)目的移動代理，使移動代理和駐留代理共存。劃分子網(wǎng)能夠節(jié)省網(wǎng)絡帶寬，而且便于對一個大型的無線自組網(wǎng)絡進行有效管理。引入駐留代理，能夠避免節(jié)點任意移動而導致拓撲信息丟失對整個網(wǎng)絡拓撲帶來的影響。

本文進一步的研究方向是將駐留代理與移動代理的比例進行精確化，并將其應用于無線傳感器網(wǎng)絡的混合式路由算法中。

參考文獻

[1] 閆永義.無線傳感器網(wǎng)絡的拓撲控制算法研究[D].西安：西安電子科技大學，2008.

[2] 丁玲，余敬東.Ad Hoc網(wǎng)中一種改進的基于移動代理的拓撲發(fā)現(xiàn)策略[C]//無線傳感器網(wǎng)及網(wǎng)絡信息處理技術(shù)：2006年通信理論與信號處理年會論文集.成都：電子科技大學通信抗干擾技術(shù)國家級重點實驗室，2006：2?7.

[3] MARWAHA S， CHEN K T， SRINIVASAN D. Mobile agents based routing protocol for mobile Ad hoc networks [C]// Proceedings of IEEE Globecom. [S.l.]： IEEE， 2002， 1： 163?167.

[4] MARWAHA S， CHEN K T， SRINIVASAN D. A novel routing protocol using mobile agents and reactive route discovery for ad hoc wireless networks [C]// 2002 10th IEEE International Conference on Networks. [S.l.]： IEEE， 2002： 311?316.

[5] AISSANI M， FENOUCHE M， SADOUR H， et al. Ant?DSR： cache maintenance based routing protocol for mobile Ad?hoc networks [C]// Advanced International Conference on Telecommunications. [S.l.]： IEEE Computer Society， 2007： 35?35.

[6] CHPUDHURY R R， BANDYOPADHYAY S， PAUL K. A distributed mechanism for topology discovery in Ad hoc wireless networks using mobile agents [C]// Proceedings of the 1st ACM international symposium on Mobile Ad hoc Networking Computing. [S.l.]： IEEE Press， 2000： 145?146.

[7] CHOUDHURY R.R， PAUL K， BANDYOPADHYAY S. Multi?agent routing protocol for mobile wireless Ad hoc networks [J]. Autonomous agents and multi?agent systems， 2004， 8： 47?68.

[8] AHMED A， FAR B. Performance of mobile agent based network topology discovery [C]// Canadian Conference on Electrical and Computer Engineering. Canada： [s.n.]， 2007： 66?69.

[9] 許力，鄭寶玉.移動自組網(wǎng)中基于移動代理的拓撲發(fā)現(xiàn)策略[J].計算機工程與應用，2003，39（29）：167?169.

[10] 魯慕瑤.Ad Hoc中基于編碼的多約束多播路由安全高效算法[J].信息通信，2015（2）：52?53.

[11] 張勝，楊鄭龍，曹凱英，等.基于移動agent的能量平衡環(huán)形路由算法[J].計算機應用研究，2014，31（9）：2661?2664.

[12] 蒲云花，陳世平.改進蟻群算法在移動自組網(wǎng)中的研究[J].計算機應用研究，2015（2）：574?578.