基于A-Star算法的Ad Hoc無線網(wǎng)絡(luò)最優(yōu)路由模型研究

劉熙明，魏 旭，竇立剛，覃洪波，楊露溪

（1.貴州航天天馬機電科技有限公司，貴州遵義563000；2.貴州大學(xué)，貴州貴陽550025）

作為一種去中心化的網(wǎng)絡(luò)技術(shù)，Ad Hoc無線自組織多跳移動通信網(wǎng)絡(luò)逐漸成為無線通信領(lǐng)域的關(guān)鍵技術(shù)。不同于圖1所示傳統(tǒng)的無線通信網(wǎng)絡(luò)，Ad Hoc無線網(wǎng)絡(luò)不需要預(yù)先架設(shè)固定的通信網(wǎng)絡(luò)基礎(chǔ)設(shè)施，這種優(yōu)勢使得Ad Hoc在戰(zhàn)場、大型營救現(xiàn)場等沒有常規(guī)基礎(chǔ)設(shè)施的情況下能夠快速靈活地實現(xiàn)無線通信，拓展了移動通信的應(yīng)用范圍，具有十分廣闊的發(fā)展前景。

圖1 具有固定網(wǎng)絡(luò)設(shè)施的無線通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

Ad Hoc網(wǎng)絡(luò)不需要固定的網(wǎng)絡(luò)基礎(chǔ)設(shè)施，每一個網(wǎng)絡(luò)節(jié)點都具有報文收發(fā)和路由的功能，節(jié)點之間可以構(gòu)成任意的網(wǎng)絡(luò)拓?fù)?，同時也可以作為網(wǎng)關(guān)接入互聯(lián)網(wǎng)中。Ad Hoc網(wǎng)絡(luò)的去中心化使得該網(wǎng)絡(luò)具有很強的抗毀重組的能力，網(wǎng)絡(luò)中的部分節(jié)點被破壞或者傳播條件發(fā)生變化時都不會造成整個網(wǎng)絡(luò)的癱瘓。

當(dāng)前對于Ad Hoc網(wǎng)絡(luò)的研究大多數(shù)是基于Ad Hoc網(wǎng)絡(luò)的協(xié)議進行仿真分析，運用到實際中的比較少，其中有關(guān)于網(wǎng)絡(luò)分簇算法及Ad Hoc網(wǎng)絡(luò)安全方面的研究。本文在此基礎(chǔ)上，以無線射頻傳輸模塊和FPGA為硬件平臺，把最優(yōu)路徑算法A-Star算法運用到無線網(wǎng)絡(luò)模型中，實現(xiàn)去中心化網(wǎng)絡(luò)的無線路由最優(yōu)化，提高數(shù)據(jù)傳輸速率，有效減少網(wǎng)絡(luò)的路由開銷。

在Ad Hoc網(wǎng)絡(luò)中所有節(jié)點都是對等節(jié)點，沒有主從之分，網(wǎng)絡(luò)采用分布式控制，將網(wǎng)絡(luò)的控制功能分散到多個節(jié)點或者全部節(jié)點中，如圖2所示。節(jié)點具有自組織功能，能夠在網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)發(fā)生變化的時候，選擇合適的參數(shù)來形成較為合理的拓?fù)浣Y(jié)構(gòu)。Ad Hoc網(wǎng)絡(luò)中的所有節(jié)點均可形成平面結(jié)構(gòu)，從源節(jié)點到目的節(jié)點通常存在多條路由，因此實現(xiàn)最為優(yōu)化的數(shù)據(jù)鏈路傳輸路由則是平面分布的Ad Hoc網(wǎng)絡(luò)節(jié)點所需要研究和解決的重要問題。

圖2 Ad Hoc網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

1 算法描述

1.1 A-Star最優(yōu)化路徑算法詳解

最短路徑問題是指在一個帶權(quán)值的圖中，尋找兩個特定節(jié)點之間一條有最小權(quán)值和路徑。假設(shè)一個無線網(wǎng)絡(luò)節(jié)點拓?fù)潢P(guān)系模型可視為數(shù)學(xué)上的賦權(quán)有向圖G=（N，A），C（P）=Ca1+Ca2+…+Can為路徑的弧長之和。則最短路徑問題就轉(zhuǎn)換為在有向圖中求解任意兩節(jié)點的最優(yōu)化路徑的問題。

雙向啟發(fā)式A-Star算法相比較傳統(tǒng)的A-Star算法，雙向A-Star算法具有時間更短的優(yōu)點。雙向A-Star算法的思想是將搜索過程分解為兩個過程，正過程從原節(jié)點到目標(biāo)節(jié)點進行搜索，而逆過程則是從目標(biāo)節(jié)點到源節(jié)點的搜索過程，正向過程的啟發(fā)函數(shù)基于目標(biāo)節(jié)點計算，逆向過程的啟發(fā)函數(shù)以源節(jié)點為基礎(chǔ)進行計算。

理論上而言，正向和逆向搜索在源節(jié)點目標(biāo)節(jié)點連線的中點相遇，但是在實際的拓?fù)浣Y(jié)構(gòu)中，由于目標(biāo)節(jié)點和原節(jié)點所處網(wǎng)絡(luò)位置的節(jié)點密度等情況不同，會造成不在中點相遇的情況。為了改善這種情況，避免算法在中間部分錯過，采用迭代式最佳節(jié)點替換法來實現(xiàn)正向和逆向啟發(fā)式搜索。具體的做法是，同時進行正向和逆向搜索，并同時生成正向和逆向最佳節(jié)點，以新生成的最佳節(jié)點為目標(biāo)節(jié)點和原節(jié)點，再次進行搜索得到二次正向、逆向最佳節(jié)點，如此反復(fù)迭代，直到相遇為止。

1.2 基于A-Star最優(yōu)化路由

由圖2可知，數(shù)據(jù)從源節(jié)點傳輸?shù)侥繕?biāo)節(jié)點，有很多種路徑可以選擇，而最優(yōu)化的路徑只有一種，此時尋找最優(yōu)路徑的問題就轉(zhuǎn)換為求有向拓?fù)浣Y(jié)構(gòu)中源節(jié)點到目標(biāo)節(jié)點最優(yōu)路徑的問題，即可運用雙向A*算法實現(xiàn)最優(yōu)化路由。

2 仿真與測試

2.1 基于A-Star最優(yōu)化路由路徑仿真

為了驗證所設(shè)計算法的可行性，在Matlab中建立仿真模型進行仿真。隨機分布80個網(wǎng)絡(luò)節(jié)點，模擬去中心化網(wǎng)絡(luò)。通過Matlab 2012Rb仿真得到結(jié)果如圖3和4所示。圖3為80個節(jié)點時的路由最優(yōu)路徑仿真結(jié)果，圖4為隨機撤掉部分節(jié)點之后的路由最優(yōu)路徑仿真結(jié)果。從圖3和圖4中可以看出，本研究所使用的算法穩(wěn)定可靠。

圖3 80節(jié)點時的仿真結(jié)果

圖4 撤去部分節(jié)點之后的仿真結(jié)果

2.2 軟件設(shè)計

軟件確保整個組網(wǎng)協(xié)議具體實現(xiàn)，使用VHDL語言編寫。系統(tǒng)上電初始化硬件接口之后，初始化自身節(jié)點地址，并把節(jié)點地址廣播出去，同時獲取來自其他節(jié)點的地址，把所有接收到的地址數(shù)據(jù)進行遍歷廣播，廣播完畢之后，所有在網(wǎng)節(jié)點之間均能收到其他在網(wǎng)節(jié)點的地址數(shù)據(jù)，所有的在網(wǎng)設(shè)備的地址構(gòu)成拓?fù)潢P(guān)系進行存儲。隨后任意節(jié)點請求數(shù)據(jù)發(fā)送，先進行路由優(yōu)化，優(yōu)化完畢之后傳輸數(shù)據(jù)。其流程如圖5所示。

圖5 軟件流程

2.3 外場測試

為了測試所設(shè)計算法的可行性，搭建了硬件測試平臺。本研究所選用的硬件架構(gòu)為無線射頻終端+FPGA，每個節(jié)點外掛一路DS18B20溫度傳感器，并能顯示10路溫度值。節(jié)點數(shù)量為10個，每個節(jié)點均能同時實現(xiàn)數(shù)據(jù)的收發(fā)控制，無線射頻傳輸模塊的有效傳輸距離為50 m。傳輸?shù)臄?shù)據(jù)為實測的環(huán)境溫度數(shù)據(jù)。

2.3.1 近距離組網(wǎng)通信測試

開機上電之后，設(shè)置8臺設(shè)備的間離為5 m，測試各節(jié)點能夠檢測到其他設(shè)備是否在線，板子上配有8路LED燈，用于指示各網(wǎng)絡(luò)節(jié)點是否成功組網(wǎng)。通過切斷電源以及增加間隔距離的方式模擬節(jié)點丟失，近距離組網(wǎng)通信測試結(jié)果如表1所示。

表1 近距離組網(wǎng)通信測試結(jié)果

2.3.2 雙跳組網(wǎng)測試

使用3個節(jié)點設(shè)備，呈直線排列，相鄰兩節(jié)點之間距離45 m，保證相鄰兩節(jié)點之間能實現(xiàn)可靠信號收發(fā)。節(jié)點1和節(jié)點3之間有效距離為90 m，無法直連通信，數(shù)據(jù)要從節(jié)點1傳到節(jié)點3，只能通過節(jié)點2中繼傳遞，實現(xiàn)雙跳數(shù)據(jù)傳輸。雙跳組網(wǎng)測試結(jié)果如表2所示。

表2 雙跳組網(wǎng)測試結(jié)果

從表2可以看出，3個節(jié)點能夠完成組網(wǎng)，節(jié)點1和3之間能夠?qū)崿F(xiàn)數(shù)據(jù)傳輸，在超出接收范圍的情況下，能通過節(jié)點2進行中繼傳輸。

圖6 節(jié)點排列結(jié)果

2.3.3 多跳組網(wǎng)以及路徑優(yōu)化測試

使用8臺節(jié)點設(shè)備，排列形狀如圖6所示。在保證節(jié)點之間距離均小于50 m的情況下，測試其路徑最優(yōu)化算法是否有效實現(xiàn)，8個節(jié)點設(shè)備在組網(wǎng)成功之后，處于靜默狀態(tài)，等待喚醒，可以通過掃頻儀實現(xiàn)去監(jiān)視8個設(shè)備的活動。設(shè)置圖6中的節(jié)點2為原節(jié)點，節(jié)點7作為目標(biāo)節(jié)點。圖6a、6b為兩種不同分布方式，而圖6c為圖6a中丟失節(jié)點5后的情況。

由圖6a中節(jié)點分布可知，從節(jié)點2到節(jié)點7的數(shù)據(jù)經(jīng)過的最優(yōu)路由為節(jié)點2→節(jié)點4→節(jié)點5→節(jié)點7。由此可知，測試結(jié)果只有2、4、5、7節(jié)點處于活動狀態(tài)，1、3、6、8節(jié)點處于靜默狀態(tài)。

由圖6b中節(jié)點分布可知，從節(jié)點2到節(jié)點7的數(shù)據(jù)經(jīng)過的最優(yōu)路由為節(jié)點2→節(jié)點3→節(jié)點4→節(jié)點5→節(jié)點6→節(jié)點7，由此可知，測試結(jié)果只有2、3、4、5、6、7節(jié)點處于活動狀態(tài)，1、8節(jié)點處于靜默狀態(tài)。

圖6c中節(jié)點分布可知，從節(jié)點2到節(jié)點7的數(shù)據(jù)經(jīng)過的最優(yōu)路由為節(jié)點2→節(jié)點4→節(jié)點6→節(jié)點7。由此可知，測試結(jié)果只有2、4、6、7節(jié)點處于活動狀態(tài)，1、3、8節(jié)點處于靜默狀態(tài)。

所有測試結(jié)果如表3所示。

表3 多節(jié)點測試結(jié)果

從表1測試結(jié)果可以看出，所設(shè)計的組網(wǎng)協(xié)議能夠基本實現(xiàn)組網(wǎng)功能，單跳、多跳數(shù)據(jù)傳輸。在網(wǎng)絡(luò)中的某一節(jié)點丟失之后，網(wǎng)絡(luò)很快實現(xiàn)路由重構(gòu)，具備很強的抗毀重組能力。在沒有數(shù)據(jù)傳輸?shù)那闆r下，各節(jié)點處于靜默狀態(tài)，有效地降低了功耗。

外場試驗結(jié)果顯示，把路徑優(yōu)化算法用于去中心化無線網(wǎng)絡(luò)中尋找最優(yōu)化路由的方法是可行的。

3 小結(jié)

本文結(jié)合Ad Hoc網(wǎng)絡(luò)的特點，以提高網(wǎng)絡(luò)中的數(shù)據(jù)傳輸速率、降低路由開銷和數(shù)據(jù)傳輸時延為目標(biāo)，提出一種基于A-Star最優(yōu)路徑算法的Ad Hoc網(wǎng)絡(luò)路由最優(yōu)化和次優(yōu)化方法。通過數(shù)值仿真試驗表明，把A-Star最優(yōu)化路徑算法運用到去中心化網(wǎng)絡(luò)Ad Hoc中尋找最短路由的方法可行。外場實驗結(jié)果表明，以A-Star最優(yōu)化路徑算法為基礎(chǔ)的網(wǎng)絡(luò)路由優(yōu)化可行有效，數(shù)據(jù)傳輸無誤碼，能夠有效地降低數(shù)據(jù)傳輸延遲、網(wǎng)絡(luò)泛洪以及網(wǎng)絡(luò)路由的開銷，提高網(wǎng)絡(luò)的抗毀重組能力，具有工程應(yīng)用價值。