基于信號方差的Ad-Hoc網絡路由算法

李 繁，張曉宇，劉 繼

(1.新疆財經大學 網絡與實驗實踐教學中心，新疆 烏魯木齊 830012；2.新疆財經大學 統計與數據科學學院，新疆 烏魯木齊 830012)

0 引 言

在Ad-Hoc無線網絡中，移動主機任意移動的特性往往造成已選定的路徑在封包傳輸的過程中，因中繼點的移動使得傳輸發生中斷，用戶收不到數據的情況，從而增加了網絡的不穩定性。即使所選擇的路徑能最快將封包送達用戶，不穩定的路徑仍會造成封包無法正確送達。另外，在移動主機的功率問題上，當中繼節點數較少的路徑被選擇后，所有數據封包會以該條路徑進行傳輸，由于該條路徑使用率太過頻繁，位于該路徑上的所有節點將會消耗更多的電量，在有限的電池容量限制下也會因為電量不足造成路徑中斷，導致傳輸失敗。

鑒于過去算法找尋最短路徑卻無法保證該路徑是否穩定的缺點，本文提出一種有效的算法，利用信號強度的變動值作為路徑選擇的條件，具有以下特點：①信號強弱表示節點之間距離的遠近，訊號越強表示兩點的距離越靠近；信號越弱，表示兩點的距離越來越遠。②Ad-Hoc網絡中的節點都是任意移動的，在一段時間內，觀測每一個節點移動的變化，即可說明節點移動的程度。若某節點的信號變動值很小，表示其移動的范圍不大，變化的程度平緩，則該節點的穩定度高。若某節點的信號變動值很大，表示其移動的范圍很大，變化程度劇烈，則該節點的穩定性很低。③以信號變動值作為選擇條件，可使路徑具有不錯的穩定度，提升封包傳輸的成功率。④所選的路徑同時具有穩定性與較短路徑的特性。

1 Ad-Hoc無線網絡路徑選擇方法

在Ad-Hoc無線網絡中，由于沒有基站的支持，移動主機常常必須記錄一些網絡信息來維持路徑的暢通，但不幸的是，這些信息卻隨著移動主機的移動而常常變動，而追蹤這些變動點一般來說可分為兩個方法，第一種稱為表驅動(table-driven)方法，只要有一個移動主機變動位置(網絡拓撲改變)，整個網絡上所有的移動主機就必須更新他們的路徑數據庫[3，4]。這種方式不僅會使移動主機負擔過重，還會造成網絡帶寬擁塞及需要大量存儲器空間的缺點，但這種方法的好處就是每個移動主機所記錄的數據都是正確而且是最新的，當需要路徑時，可以直接從內存中尋找，立刻建立聯機；另一種方法稱為需求導向(on-demand)方法，顧名思義，就是需要路徑的時候再開始去尋找，但由于路徑找法是需要的時候才開始尋找，所以會有無法達到實時性的缺點，其優點就是不必一直更新內存內的路徑表，并且不需用太多的內存空間來記錄網絡信息[5]，這兩種方法各有優缺點，許多研究根據這兩種方法提出不同的路由技術。本文以table-driven及on-demand為前提，將路由方法整理成三大類。

第一類是最短路徑路由技術[6]。此類的路徑選擇是以該路徑經過的中繼點較少者為優先考慮，例如C.E. Perkins等提出的DSDV方法，是基于傳統Bellman-Ford路由選擇算法改良而發展出來的。一個以路由表(routing table)為基礎的路由通信協議，意指每一個行動節點必須儲存一個路由表，其中記錄所有與該節點可能進行鏈接的節點及距離，路由表內的每筆記錄同時也包含了一組序列號碼(sequence number)，用來判斷該筆數據的新舊情況，以避免各行動節點交換路徑信息時發生拓撲結構改變，而產生“無窮計數”(count to infinity)的問題。另外，C.E. Perkins等又提出了AODV的方法。AODV 是以on-demand的路徑建立方式，不同于DSDV通過網絡拓撲狀態改變來驅動路徑信息的機制，只有在需要某端點路徑信息的情況下，才對該端點進行路徑尋找與建立的動作，不需固定周期性的去維護路徑信息[7，8]。CGSR是建構在DSDV之上的路由協議。CGSR的機制是將整個網絡劃分成數個集群(cluster)，每個集群中選出集群管理者(cluster head)，由他們來負責管理集群內的成員和交換重要的相關信息，和記錄整個網絡的架構，這種方式是以table-driven為導向，非集群管理的節點就不必記錄這些信息，如此一來，整個網絡的每個節點所記錄的總數據量就可以大大的減少。TORA將鏈接方向逆轉(link reversal)的觀念運用在Ad-Hoc無線網絡上，是一種分布式的路由算法，非常適合在高度動態的環境下使用[9，10]。

第二類是利用全球衛星定位系統與Ad-Hoc無線網絡路由協議結合應用。其相關研究有LAR、GRID等路由技術[11，12]。LAR(location-aided routing)利用GPS的位置信息來達到改善Ad-Hoc無線網絡路由選擇的效能。LAR的作法在于縮小尋找路徑時的廣播范圍，同時又不影響其路徑的找尋。首先假設每一個節點已知自己目前的位置，同時源節點知道目的節點在t0的位置L及目前的時間為t1并且假設源節點知道目的節點的平均速度V。有了這些信息，源節點可以由此推測出目的節點目前會在那個區域內，因此就可以得知預測區域(Expected Zone)。畫出預測區域之后就可得知欲廣播的范圍，就是所謂的尋求區域(Request Zone)[13，14]。GRID協議通過衛星定位系統將網絡分割成很多四方格且每個格子中選出一個靠近中心點的網關節點來記錄格子內部的路由表，負責區域內部的通信，使用table-driven的方式。當網關節點要離開格子時就將路由表廣播給格子內的其他成員，再由成員中選出代替的網關節點。區域之間的通信必須經由網關節點，使用on-demand的方式，除了源主機和目的主機之外，路徑的中間點必為網關節點。

第三類是以路徑穩定性(stability-based)為基礎的路由技術，代表路由技術有ABR及SSA。ABR(associativity-based routing)的設計主要著眼于Ad-Hoc無線網絡里節點間不穩定的鏈接關系，因此采用了關連(associativity)穩定性的概念，用來表示一個節點相對于相鄰節點的鏈接的穩定程度。SSA(signal stability based adaptive routing)為on demand的路由技術，是以信號強度決定節點是否處于穩定狀態，并且尋找一條能夠維持一段時間而不斷線的路徑[15，16]。

2 以信號方差為基礎的路由協議

本文提出了以信號方差為基礎的路由選擇算法SVR(signal variance based routing)。

2.1 協議概要

SVR是以信號方差為基礎的路由算法，不同于過去Ad-Hoc無線網絡路由算法中找尋最短路徑的做法，SVR是以路徑穩定性作為首要考慮的條件。在Ad-Hoc無線網絡中，網絡上的節點每隔一段時間會發出beacon與鄰近節點通信。所謂beacon是指“我還活著”(I am alive)的信息，每隔一段時間，無線設備會交換此信息，用來維護彼此的聯機狀態。通過beacon得知節點之間的信號強度后，并紀錄每一個節點的信號方差，再將此信號方差與節點的最大可通信范圍(radio transmission range)做計算，得到一個鏈接穩定值(link stability value)之后記錄在信號方差表(signal variance table，SVT)中。當來源節點需要路徑時，會發出路徑請求(route request)封包給鄰近的節點，而鄰近節點收到路徑請求封包，若先前沒有處理過該封包，則將記錄在信號變動表中的鏈接穩定值存于封包中繼續廣播給鄰近節點，直到送達目的節點為止。當目的節點收到來自不同地方傳送過來的路徑請求封包，計算每一條路徑中所有鏈接的鏈接穩定值相乘的結果，值越大者，表示該路徑的穩定性高，位于該路徑上節點變動平緩；反之，值越小者，表示該路徑的穩定度不高，位于該路徑上的節點變動較大。因此，目的節點將以鏈接穩定值較大的作為路徑的選擇。目的節點選擇了最穩定的路徑后，沿著所選擇的路徑送出路徑回復(route reply)封包，直到源節點為止。

2.2 協議細節

Ad-Hoc無線網絡中，所有節點借著每隔一段時間發出的beacon與鄰近節點通信，可得知節點間的信號強度。將收到的信號強度數據，利用式(1)及式(2)可得某鄰近節點的信號平均強度值SSavg及信號方差值SSvar。t是指收到beacon的總次數，為時間單位；而S1…St是指紀錄第一次beacon的信號強度值，到第t次的信號強度值

(1)

(2)

節點間的信號強度與距離的關系，以H.T. Friis提出的式(3)來看，Pr是指接收端的信號強度，Pt是指發送端的信號強度，Gt、Gr分別表示當發送端、接收端信號衰減時，用來增強信號強度的參數值，λ是指信號的波長，L指系統損失(system loss)，d是指發送端與接收端的距離。由公式可知信號強度與距離的平方有關系

(3)

信號方差是指節點間的位置移動情形，信號方差越大，表示每次beacon記錄的信號強度不穩定，若節點A固定時間發出beacon給鄰近節點B，偵測到的信號強度有強有弱，表示節點B忽而走遠、忽而走近，因此節點B并不是一個穩定的節點，所計算出來的信號方差就會很大。若節點A偵測到節點C的信號強度值維持在一個平均值，表示節點C的位置變動平緩，計算出來的信號方差將會很小。由于每次 beacon都會產生一個新的信號強度值，若每得到一個新的信號強度值都要與舊的信號強度值重新計算，將會消耗許多計算機資源，例如內存空間、電池電量等，而且重新計算所花費的時間也會造成網絡效能的延遲(delay)效應。因此，我們推導一個容易計算信號平均值與信號方差的公式(式(4)與式(5))，只要將新的信號強度值帶入即可算出新的信號方差，如此可快速找尋一條穩定的路徑，以利數據封包的快速傳送，減少延遲的時間

(4)

(5)

假設收到新的信號強度值St+1，將此值帶入式(4)、式(5)并與前次計算出來的信號方差SSvar及信號平均值SSavg做計算，即可得到新的信號方差NewSSvar及NewSSavg，最后再將新的SSvar及SSavg存放于SVT的SSvar與SSavg字段中。每個節點都維護著信號方差表，包含移動節點、Clicks、SSavg、SSvar、LSV等5個字段。

Clicks表示連續收到beacon的次數，每收到一次，則Click加1，若預期應收到beacon而未收到時，表示鄰近節點已遠離通信范圍，此時則將Click設為0。LSV(link stability value)為一預估機率值，代表聯機不中斷的成功率，當LSV越高，表示兩點間的鏈接(link)越穩定，越不容易斷線；反之，若LSV越低，表示兩點間的鏈接不穩定，隨時都有可能斷掉。本文提出兩種LSV的計算方式：LSVSVR1及LSVSVR2。LSVSVR1是以信號平均強度為參數值所計算的機率值；而LSVSVR2是以信號變異值為計算LSV的參數值。以下將對于這兩種方式做詳細的說明。第一種方式是以信號平均強度為參數值，稱為LSVSVR1。假設節點A最大可通信范圍為Dradius，節點B的移動位置位于節點A的Dradius上，也就是說節點B的移動可能隨時超出節點A的Dradius外，造成節點A無法與節點B通信的情形，如果在節點A所得到的節點B平均信號強度為SSavg，經由式(3)距離與信號強度的關系可推得節點A與節點B的平均距離為Davg1，Davg1等于Dradius時，節點A、B之間的LSVSVR1趨近于0；同樣，另一節點C位于節點A的Dradius內，越靠近節點A，表示節點C移動的范圍一直在節點A的附近，則節點A與節點C的LSVSVR1趨近于1，因此Davg2就越小，我們應讓LSVSVR1越大。如圖1所示。

圖1 信號平均強度與鏈接穩定值的關系

以上是以距離的觀點解釋距離與穩定度的關系，而以信號強度的觀點，SSavg若越大，代表距離越近(Davg越小)，因此LSVSVR1越大，假設SSmax代表每一節點可能收到的最大強度，我們推導出以信號強度平均值為基礎的鏈接穩定度計算式(6)，由已知節點的平均信號強度值SSavg，即可算出LSVSVR1

(6)

除了平均信號強度值可用來解釋節點信號與鏈接穩定值之間的關系外，另外，我們也利用信號強度變動值來說明節點的信號變動與鏈接穩定值之間的關系。第二種是以信號變異值為參數，稱為LSVSVR2。假設某一節點移動較劇烈，對于另一節點的觀測范圍，此節點信號變動的范圍最大將為SSmax，亦即此刻信號強度為SSmax，下一時刻信號強度可能立即為接近0的值，此種情形為信號最不穩定的情況。在一極端的情況下，所有的beacon中一半信號強度為SSmax，另一半的信號強度為0時，其信號強度的變動值SSvar不會超過SSmax/2上限值。由此可知，當信號方差SSvar等于SSmax/2時，我們將LSVSVR2值設為0，意指當節點變化越劇烈，它的信號方差很大，SSvar越大，則鏈接越不穩定，所計算出來的鏈接穩定值越小。反之，當信號方差SSvar等于0時，其LSVSVR2等于1，意指當節點變化越平緩，它的信號方差很小，SSvar越小，則鏈接越穩定，所計算出來的LSVSVR2越大。因此，我們可推導出式(7)，得知節點的信號方差SSvar，即可計算出LSVSVR2

(7)

2.3 路徑搜索與回復程序

2.3.1 路徑請求、回復封包格式

圖2為路徑請求封包格式，SEQ為一序列號碼，一個節點可能同時收到不同來源的封包，序列號碼用來判斷封包是否先前處理過，一旦處理過該封包，則直接將封包丟棄(drop)，不再繼續廣播下去。TYPE為封包類型，包含UNICASTDATA、FLOODDATA、ROUTESEARCH、ROU-TEREPLY等類型。SRC及DEST分別為源節點的地址及目的節點的地址。TTL(time to live)指封包的存活時間，避免因封包產生錯誤而發生無窮循環(loop)的現象。HOP指經過的節點數。IN是指中間節點的地址，每經過一個節點，記錄該節點的ID。METRIC存放LSV，當節點收到封包時，將記錄在信號變動表中的鏈接穩定值儲存在此字段，作為路徑選擇的判斷條件。CRC(cyclic redundancy check)利用checksum來檢查封包是否有錯誤。當某節點發出路徑請求封包時，TYPE值為ROUTESEARCH代碼，剛開始HOP為0，IN、METRIC字段不存在，路徑請求封包每經過一個節點HOP值加1，IN、METRIC字段也會各多一筆。

圖2 路徑請求、回復封包格式

2.3.2 路徑搜索程序

當節點S欲傳送數據給節點D時，節點S會先將自己的地址及目的節點地址等信息存放于路徑請求封包中，再將該封包廣播給鄰近節點A、B，節點A、B收到該封包后判斷是否先前處理過封包，若無，則繼續廣播給鄰近節點，若已處理過，則直接丟棄該封包，不再繼續廣播下去。當節點A收到封包時，將其ID及LSV分別儲存在IN及METRIC字段，如此進行下去，每個節點都將自己的ID及LSV儲存在路徑請求封包中，當目的節點D收到來自不同地方的封包后，根據存放于封包中的ID及METRIC字段，得到多條路徑數據，通過式(8)LSV的相乘得到一路徑穩定值PSV(path stability value)，值越大者，表示路徑越穩定。如圖3所示。

圖3 路徑搜索程序

將LSV相乘的另一層意義在于：當越多的LSV相乘，由于每一LSV值小于1，所得到的PSV將越小，而越少的LSV相乘，所得的PSV越大。因此，我們最終選擇一條PSV最大的路徑，不但為最穩定的路徑，同時也會是一條較短路徑。因此，我們所提的路徑選擇方法，不僅確保路徑的穩定度，也不會帶來過大的通信延遲

PSV=LSV1×LSV2×…×LSVn

(8)

2.3.3 路徑回復程序

決定最穩定的路徑后，目的節點會往源節點方向送出路徑回復封包(route reply packet)，當源節點收到該封包，表示節點S與節點D的路徑已確定，立即開始做數據傳送的動作。

2.4 范 例

圖4為一ad hoc無線網絡環境范例。網絡上的每個節點都維護信號方差表，通過每段時間發出的beacon與鄰近節點通信，可得知信號的變化，將得到的信號值計算出平均信號強度、信號方差及鏈接穩定值后，記錄在信號方差表中，如節點A的信號方差表見表1。

表1 節點A的信號方差

圖4 簡單Ad-Hoc無線網絡范例

當節點S需要一條到達節點D的路徑時，節點S會發出路徑請求封包給節點A、B，節點A收到封包，將LSV

及ID儲存于路徑請求封包的字段中，繼續再將此封包廣播下去，直到目的節點D收到此封包為止。節點D收到來自不同地方的路徑請求封包，包含多條的路徑數據，見表2。

表2 多條路徑數據

當節點 D收到多條路徑數據，將記錄在封包里的LSV相乘，得到每條路徑相乘后的PSV，值越大者表示該路徑與其它路徑比較起來較穩定，因此在這個例子當中，節點D會選擇Path_4，而Path_4同時也是5條路徑中的最短路徑。決定路徑后，節點D傳送路徑回復封包，直到來源節點S收到該封包，立即可做數據流的傳送與接收。

3 實驗分析

這里我們提出實驗數據將SVR與最短路徑算法及R.Dube等提出的同以信號穩定度為基礎的SSA算法作比較。本文的比較對象-最短路徑算法，泛指AODV、DSR等算法。我們針對路徑的持續時間、找到路的機率與路徑經過的hop數等進行一系列的比較。以下將說明我們在模擬之前所必須提出的假設和模擬的環境。最后，則是一些仿真結果的數據及分析。

3.1 模擬環境假設

在我們的研究中，仿真環境僅限于網絡層(network layer)，對于數據鏈路層(data link layer)的細節，如MAC協議、多重存取所造成的干擾(multiple accessinterference)、功率下降、鏈接錯誤(link error)，并不加以考慮。而物理層以及信道(channel)的細節問題，也不加以考慮。也就是說，兩個節點互相在傳輸范圍內時，即可成功傳送數據，反之，則接收不到數據。本文之所以不考慮上述狀況，是因為以上問題可以用現有的IEEE 802.11等類似的通信協議加以解決，只要將本文建構在IEEE 802.11的協議之上，即可解決上述問題。

3.2 模擬環境參數設定

以下介紹模擬環境所設定的參數：

仿真區域大小：670m×670m

移動主機個數：50～200個

傳輸半徑：150 m

模擬時間：100 s

移動速度：10～50 m/sec

移動模式：360度任意移動

Beacon 區間：2 s

節點移動比例：20～80%

3.3 仿真數據分析

3.3.1 穩定度分析

節點的個數、節點移動比例及節點移動速度都是影響路徑穩定度的因素。我們利用SVR1、SVR2、ST這3種路由機制所找出來的路徑，計算其在100 s的運行時間內，路徑持續而不中斷的時間，作為穩定度分析。SVR1、SVR2兩種都為本文所提出的路由機制，其中SVR1是以信號平均強度作為計算LSV的參數值；而SVR2是以信號變異值作為計算LSV的參數值。ST是傳統找尋最短路徑(shortest path)的機制。我們針對節點移動速度的變化與路徑持續時間進行模擬，將產生出來的數據制成見表3。

表3 節點移動速度與路徑持續時間數據

在100 s的執行內，SVR1、SVR2路徑持續時間長于ST時間及SVR1路徑持續時間長于SVR2時間等會因為節點移動速度增加而使路徑持續不中斷的時間降低，原因在于當節點的移動速度加快，節點移動很容易超過可通信范圍，導致路徑的中斷，因此節點移動速度越快，則路徑持續時間越短。在節點移動速度為10的情形下，SVR1的路徑持續時間高出傳統ST的路徑達近98%，而SVR2也高達近81%；而在節點移動速度為50的情形下，SVR1的路徑持續時間高出傳統ST的路徑達近81%，而SVR2也高達近69%。由此可知，本文提出的兩種機制，在路徑穩定度方面與傳統路由機制比較均有不錯的表現。如圖5所示。

圖5 節點移動速度與路徑持續時間關系

在節點的數目與路徑穩定度的實驗中，我們將節點數目與 SVR1、SVR2、ST這3種機制的路徑持續時間制成見表4。

表4 節點數量與路徑持續時間數據

節點數目越多，找到穩定的節點機率越高，因此以穩定度為優先考慮的SVR1及SVR2找到的路徑持續時間會越長。當節點個數為50時，SVR1的路徑持續時間高于ST達91%，SVR2的路徑持續時間高于ST達86%；而在節點個數為200 時，SVR1的路徑持續時間高于ST可達93%，SVR2的路徑持續時間高于ST達88%。因此，節點數越多，SVR1、SVR2均有不錯的表現。如圖6所示。

穩定度分析的最后一個實驗中，我們將670m×670m范圍內的100個節點，假設其移動比例為20%～80%之間。移動比例為20%的條件下，表示100個節點中，有20個是屬于較不會移動的節點，移動范圍均在通信范圍內，其它80個是屬于較會移動的節點，移動范圍可能隨時超過通信范圍。通過此參數的設定，觀察不同的節點移動比例與穩定度的關系。在移動比例為20%的情形下，SVR1的路徑持續時間高于ST達90%，SVR2的路徑持續時間高于ST達84%；在移動比例為80%的情形下，SVR1的路徑持續時間高于ST達96%，SVR2的路徑持續時間高于ST達78%，SVR1及SVR2的路徑持續時間高于ST的比例均維持在一個值，并沒有太大的變化。原因在于，當變化不大的節點數越多，找到穩定的節點越容易，因此路徑就越穩定。所以當節點移動比例值越高，表示較不會移動的節點數越多，ST的路徑持續時間相對的提高。如圖7所示。

圖7 節點移動比例與路徑持續時間關系

3.3.2 路由選擇成功率分析

在此實驗當中，執行100 s的時間內，我們針對4種路由機制可以成功找到路徑的機率作比較。SVR1、SVR2、ST這3種機制在運行時間內，皆可以100%找到路徑，而SSA利用信號強弱來找路徑的機制最多只有將近20%找到路徑，其余80%因為不符合SSA選擇路徑的條件而沒有被選到。因此，當源節點需要路徑時，采用SSA的機制將會很容易找不到一條適合的路徑，導致無法做數據的傳送與接收。圖中可發現，當節點的移動速度越高，SSA找到路徑的機率也隨之增加。原因在于節點的移動速度越高，移動范圍很容易進入另一節點的通信范圍內，當另一節點正在找尋合適的節點時，該移動節點位置正好處于另一節點的旁邊，對另一節點而言，該移動節點的信號強度非常強，以SSA的選擇條件，則該移動節點會被選擇到。但整體而言，SSA找到的路徑的機率還是偏低。

3.3.3 路徑長度分析

此實驗在觀察于不同的節點移動速度當中，SVR1與SVR2每次找到的路徑長度與ST所找到的最短路徑作比較。本文提出的方法偏重于“穩定度”的概念，也就是所找的路徑將有穩定，不易斷線的特性，而經過的hop數為次要考慮的條件。實驗結果發現，SVR1與SVR2的路徑長度只多于最短路徑一個hop數。利用SVR1或SVR2與ST的路徑長度比例得知，無論節點移動速度的快或慢，SVR1的路徑長度皆多于ST的路徑長度一個hop數；而SVR2的路徑長度幾乎與ST的路徑長度一致。因此，本文提出的路由機制，不僅具有路徑穩定的特性，路徑長度也不會太長，一旦選擇SVR1或SVR2作為路由機制，則在數據傳輸上將有不錯的效能表現。

4 結束語

本文提出on-demand的路由選擇算法，目的在于找一條最穩定且不易中斷的路徑作為數據的傳輸信道，顛覆傳統以最短路徑為主要考慮的觀念。由實驗結果發現，本文提出的兩種機制在及路徑成功率及路徑穩定度上均有不錯的表現，而在路徑的長度方面，與傳統最短路徑的機制比較，相差無幾。因此，本文提出的機制同時具有路徑穩定及最短路徑的特性，在數據傳輸的效能上，將是不錯的路由選擇機制。下一步，我們將進行路徑維護機制的研究，對于路徑中斷、路徑修復等問題提出行之有效的解決辦法。