王仁紅，廖惜春，郭洪威

?

改進的A*算法在Ad Hoc網(wǎng)絡(luò)中的應(yīng)用

王仁紅，廖惜春，郭洪威

（五邑大學(xué) 信息工程學(xué)院，廣東 江門 529020）

針對Ad Hoc網(wǎng)絡(luò)拓撲結(jié)構(gòu)頻繁變動，已有路由的有效時間短、丟包率高等問題，將改進的A*算法應(yīng)用于Ad Hoc網(wǎng)絡(luò)實現(xiàn)路由查找，利用NS2仿真，將A*算法與傳統(tǒng)的AODV、DSR路由算法在丟包率、傳輸速率、平均端到端時延、算法開銷等4個方面進行性能比較，仿真結(jié)果表明：A*算法在源節(jié)點與目的節(jié)點間尋找路由的過程中，能夠快速而準(zhǔn)確地建立路由，在路由速度、發(fā)包成功率等方面有明顯的提升.

Ad Hoc網(wǎng)絡(luò)；A*算法；路由查找；發(fā)包成功率

1 A*算法的基本原理

A*算法通過OPEN和CLOSE表選擇、保存節(jié)點，其中，OPEN表是路由查找過程中的一個鏈表，用來保存最終的路由路徑，CLOSE表記錄已訪問過的節(jié)點. 首先將起始點放入OPEN表，CLOSE表置空，算法開始，其主要思路用C++語言格式表述如下：

1）若OPEN表不為空，從表頭取一個結(jié)點，該節(jié)點可能是目標(biāo)節(jié)點，也可能只是當(dāng)前Ad Hoc網(wǎng)絡(luò)中的一個普通節(jié)點，若OPEN表為空，則失敗退出；

2）判斷是否為目標(biāo)解，如果是，終止算法；否則進行下一步；

2 基于改進A*算法的Ad Hoc路由算法

2.1 改進的A*算法描述

A*算法廣泛應(yīng)用于有線網(wǎng)絡(luò)最優(yōu)路徑求解以及一些策略設(shè)計中，在無線Ad Hoc網(wǎng)絡(luò)的路由查找過程中，需要對A*算法做如下改進.

a）把上述第3步替換為“將的所有與父節(jié)點直接相連的下一層子節(jié)點放入OPEN表中（程序代碼為p->node=），同時把放入CLOSE表中，計算啟發(fā)式函數(shù)值，保存在節(jié)點信息中，并且用后向指針指向的當(dāng)前節(jié)點即父節(jié)點，用于從目標(biāo)點回溯，確定最終的路由，然后返回步驟1”.

我們經(jīng)常講，領(lǐng)導(dǎo)干部必須德才兼?zhèn)?。但德與才的位置不是平起平坐的，德者才之帥也，才者德之資也。改革開放和現(xiàn)代化建設(shè)，無疑要求干部必須具備多方面的知識、才能和本領(lǐng)，但政德永遠是第一位的，沒有高尚的政德，知識再多、才能再高、本領(lǐng)再大，可能做的錯事、壞事更多更大，對百姓和社會的危害尤烈，反腐落馬的或虎或蠅，此類反面典型不可謂不多，落馬官員中不乏懂經(jīng)濟、會管理的高級人才，甚至是經(jīng)濟學(xué)者、銀行高管、高鐵專家等等，滿腹經(jīng)綸、身手不凡，但操守有虧，對黨不忠，對民不誠，品行不端、自甘墮落，以人生敗筆畫上句號，當(dāng)然也毀了事業(yè)。

Ad Hoc網(wǎng)絡(luò)中的路由算法歸根到底是找出源節(jié)點到目的節(jié)點之間的路由，實現(xiàn)快捷有效的通信，改進后A*算法路由算法的路由保存在OPEN表里. 本文提出的改進型A*算法主要有2個過程：一個是從源節(jié)點進行廣度搜索[8]，即從初始狀態(tài)逐層向下尋找，直到找到目標(biāo)節(jié)點為止，其中刪除了不能擴展的（非目的）節(jié)點，以降低算法復(fù)雜度；另一個是從目標(biāo)節(jié)點至源節(jié)點進行回溯，從而確定最后的路由. 具體步驟如下：

1）首先把源節(jié)點和與源節(jié)點通信范圍內(nèi)的節(jié)點放進OPEN表（按節(jié)點與源節(jié)點之間的估價函數(shù)值升序排列），并清空CLOSE表，再將源節(jié)點放進CLOSE表中；

2）如果OPEN表為空，則退出算法，查找失?。环駝t轉(zhuǎn)步驟3）；

3）從表頭取一個節(jié)點，如果該節(jié)點的子節(jié)點不在OPEN表中，則把該節(jié)點的子節(jié)點按照評估函數(shù)值升序排列. 該節(jié)點可能是目標(biāo)節(jié)點，也可能只是當(dāng)前Ad Hoc網(wǎng)絡(luò)中的一個普通節(jié)點，判斷是目標(biāo)解嗎？如果是，終止算法，否則下一步；

4）把節(jié)點放進CLOSE表中同時把的估價函數(shù)值也放進CLOSE表中，令指向“源節(jié)點”，即該節(jié)點的前驅(qū)節(jié)點，循環(huán)判斷節(jié)點的所有子節(jié)點，如果是目標(biāo)節(jié)點則退出循環(huán)，否則判斷是否是葉子（無子節(jié)點的）節(jié)點，如果是，則刪除該節(jié)點，否則轉(zhuǎn)向步驟3）；

5）清空OPEN表，在CLOSE表中，從目的節(jié)點開始，沿著后續(xù)節(jié)點回溯，直到源節(jié)點，把這條路徑中的節(jié)點按照順序放進OPEN表作為最終的路由路徑（如果回溯的過程中發(fā)現(xiàn)有一節(jié)點退出網(wǎng)絡(luò)，則選擇次優(yōu)節(jié)點進行回溯）.

2.2 啟發(fā)式函數(shù)的選擇

圖1 一個最小跳數(shù)路由的示意圖

2.3 路由選擇的數(shù)據(jù)包格式

改進后的A*算法數(shù)據(jù)包格式包括：源地址、源位置、目標(biāo)地址、目標(biāo)位置、次優(yōu)節(jié)點的信息、CLOSE表中全部節(jié)點的信息. 它比經(jīng)典算法增加了次優(yōu)節(jié)點信息字段以提高路由速度. 次優(yōu)節(jié)點信息包含節(jié)點指示信息、父節(jié)點指示信息以及估價函數(shù)的代價；CLOSE表中全部節(jié)點的信息包含搜索節(jié)點的指示信息、父節(jié)點的指示信息以及估價函數(shù)代價；源地址就是源節(jié)點的IP地址；源位置是源節(jié)點的物理位置；目標(biāo)地址是目標(biāo)節(jié)點的IP 地址；目標(biāo)位置是指目標(biāo)節(jié)點的物理位置.

3 仿真及結(jié)果

在Windows XP+CygWin+NS2.33軟件環(huán)境下，對上述改進的A*算法與AODV、DSR算法進行對比仿真.

實驗中的網(wǎng)絡(luò)拓撲分別由5、10、20…100個節(jié)點組成，這些節(jié)點隨機分布在1 000 m×1 000 m區(qū)域內(nèi)，形成Ad Hoc網(wǎng)絡(luò)，鏈路帶寬為1 Mbit/s，仿真通信采用大小為512 byte的定長數(shù)據(jù)包，節(jié)點最大移動速率為10 m/s，路徑的端節(jié)點隨機選出. 實驗中，對每組參數(shù)都進行了10次仿真實驗，并取其平均值作為考察依據(jù).

3.1 節(jié)點數(shù)目和對應(yīng)丟包收包比的關(guān)系

不同節(jié)點數(shù)目下3種算法的丟包收包比的比較如圖2所示. 從圖2可以看出：隨節(jié)點數(shù)目的增多，3種算法的丟包收包比都有所上升，但DSR升得相對快一些；A*考慮了節(jié)點的剩余能量，通過平衡各個節(jié)點的能量消耗延長網(wǎng)絡(luò)的生存時間，保證了更多的數(shù)據(jù)得以傳輸；AODV相對較好一些，但它僅維護一條到目的節(jié)點的路由，在一定程度上影響了成功率.

圖2 發(fā)包成功率隨節(jié)點數(shù)的變化圖

3.2 停留時間對算法性能的影響

不同停留時間各算法的性能比較如圖3所示. 圖3-a是不同停留時間下各算法的平均端到端傳輸時延，DSR的延遲時間較長，A*的傳輸時延比AODV要短一些，這是由于A*在路由查找過程中及時有效地去除了不需要的路由信息（非最優(yōu)的節(jié)點和路徑）. 不同停留時間下各算法開銷如圖3-b所示，3種算法的算法開銷隨著停留時間的增加相應(yīng)地減少，最后都趨向平穩(wěn)，DSR算法開銷明顯高于AODV和A*，AODV與A*則幾乎相同（AODV稍微高一點）.

圖3 停留時間對算法性能的影響

3.3 丟包與收包的比率和傳輸速率之間關(guān)系

不同算法的丟包與收包的比率和傳輸速率的關(guān)系如表1所示（表中數(shù)據(jù)是在節(jié)點數(shù)為50的條件下的仿真結(jié)果），由表1可知：隨著傳輸速率的增加，A*算法數(shù)據(jù)包的接收數(shù)目迅速增加，當(dāng)傳輸速率大于300 kb/s時，丟包與收包的比例也迅速逼近0；DSR的丟包收包比下降最為緩慢，在較高速率（500 kb/s及以上）時逼近0.

表1 不同算法的丟包與收包的比率和傳輸速率的關(guān)系

4 結(jié)束語

本文結(jié)合A*算法提出了一種自適應(yīng)的Ad Hoc按需路由選擇算法，與其他Ad Hoc網(wǎng)絡(luò)路由技術(shù)相比，本算法具有如下優(yōu)勢：1）算法不需要事先知道網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，利用通信范圍能確定所有的網(wǎng)絡(luò)節(jié)點，且利用啟發(fā)式搜索發(fā)現(xiàn)節(jié)點，獲得近似最優(yōu)的路由路徑；2）算法有良好的可擴展性和自適應(yīng)性，能夠獨立完成無線Ad Hoc網(wǎng)絡(luò)的路由選擇功能，并進一步能夠避免廣播風(fēng)暴；3）在啟發(fā)式函數(shù)的作用下，算法不僅能夠發(fā)現(xiàn)最優(yōu)路徑，還避免了貪心算法導(dǎo)致的局部最優(yōu)問題；4）算法簡單易行，效率高. 仿真實驗證明，本算法具有良好的路由查找性能、降低了端到端的延遲、算法開銷等，具有良好的可擴展性和自適應(yīng)性.

[1] MERKLE D, MIDDENDORF M, SCHMECK H. Ant colony optimization for resource-constrained project scheduling[J]. IEEE Transactions on Evolutionary Computation, 2002, 8(4): 333-346.

[2] ZOU Liang, XU lianmin, ZHU Lingxiang. Implement of A* algorithm and its application in shortest path problem in dynamic networks[J]. Journal of Shenzhen University: Science and Engineering, 2007, 24(1): 32-36.

[3] 沈輝，石冰心，鄒玲，等. Ad Hoc網(wǎng)中基于熵的長壽分布式QoS路由算法[J]. 軟件學(xué)報，2005, 16(3): 445-452.

[4] KO Y B, VANDYA N H. Location-aided routing in mobile Ad Hoc networks[J]. Wirelesnetworks, 2000, 6(4): 307-321.

[5] YANG Suqiong, LIN Biqin, HE wei. Implementation of search for map path based on A* algorithm[J]. Railway Computer Application, 2000, l9(4): 8-11.

[6] 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)：C語言版[M]. 北京：清華大學(xué)出版社，1992.

[7] 郭亞軍，魯漢榕. 動態(tài)環(huán)境中的一種實時啟發(fā)式搜索算法[J]. 空軍雷達學(xué)院學(xué)報，2000, 14(4): 58-60.

[8] 謝希仁. 計算機網(wǎng)絡(luò)[M]. 5版. 北京：電子工業(yè)出版社，2008.

A Study of the Application of the A* Algorithm in Ad Hoc

WANGRen-hong, LIAOXi-chun, GUOHong-wei

In light of the frequent structural changes of the Ad Hoc network topology, short duration of the effective route and the high packet loss rate, we applied the improved A* Algorithm to the Ad Hoc networks to achieve routing lookup. We compared the A* Algorithm and the traditional AODV and the DSR routing algorithms using NS2 simulation in the four aspects of algorithm performance: packet loss rate, transmission rate, average end to end delay and algorithm overhead. Simulation results show that the A* algorithm can quickly and accurately establish the route in the routing process from source node to destination node and can significantly increase the routing speed and the success rate of sending packets.

Ad Hoc network; A* algorithm; routing lookup; packet-sending success rates

1006-7302（2011）02-0038-05

TN915.04

A

2010-12-15

廣東省科技計劃項目（2009B010800012）

王仁紅（1982—），女，湖南邵陽人，碩士研究生，主要研究無線傳感網(wǎng)絡(luò)及數(shù)據(jù)處理；廖惜春，教授，碩士生導(dǎo)師，通信作者，主要研究無線傳感網(wǎng)絡(luò)及數(shù)據(jù)處理.