基于信號方差的Ad-Hoc網(wǎng)絡(luò)路由算法

李 繁，張曉宇，劉 繼

(1.新疆財經(jīng)大學(xué) 網(wǎng)絡(luò)與實驗實踐教學(xué)中心，新疆 烏魯木齊 830012；2.新疆財經(jīng)大學(xué) 統(tǒng)計與數(shù)據(jù)科學(xué)學(xué)院，新疆 烏魯木齊 830012)

0 引 言

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

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

1 Ad-Hoc無線網(wǎng)絡(luò)路徑選擇方法

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

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

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

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

2 以信號方差為基礎(chǔ)的路由協(xié)議

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

2.1 協(xié)議概要

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

2.2 協(xié)議細節(jié)

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

(1)

(2)

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

(3)

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

(4)

(5)

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

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

圖1 信號平均強度與鏈接穩(wěn)定值的關(guān)系

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

(6)

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

(7)

2.3 路徑搜索與回復(fù)程序

2.3.1 路徑請求、回復(fù)封包格式

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

圖2 路徑請求、回復(fù)封包格式

2.3.2 路徑搜索程序

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

圖3 路徑搜索程序

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

PSV=LSV1×LSV2×…×LSVn

(8)

2.3.3 路徑回復(fù)程序

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

2.4 范 例

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

表1 節(jié)點A的信號方差

圖4 簡單Ad-Hoc無線網(wǎng)絡(luò)范例

當(dāng)節(jié)點S需要一條到達節(jié)點D的路徑時，節(jié)點S會發(fā)出路徑請求封包給節(jié)點A、B，節(jié)點A收到封包，將LSV

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

表2 多條路徑數(shù)據(jù)

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

3 實驗分析

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

3.1 模擬環(huán)境假設(shè)

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

3.2 模擬環(huán)境參數(shù)設(shè)定

以下介紹模擬環(huán)境所設(shè)定的參數(shù)：

仿真區(qū)域大?。?70m×670m

移動主機個數(shù)：50～200個

傳輸半徑：150 m

模擬時間：100 s

移動速度：10～50 m/sec

移動模式：360度任意移動

Beacon 區(qū)間：2 s

節(jié)點移動比例：20～80%

3.3 仿真數(shù)據(jù)分析

3.3.1 穩(wěn)定度分析

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

表3 節(jié)點移動速度與路徑持續(xù)時間數(shù)據(jù)

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

圖5 節(jié)點移動速度與路徑持續(xù)時間關(guān)系

在節(jié)點的數(shù)目與路徑穩(wěn)定度的實驗中，我們將節(jié)點數(shù)目與 SVR1、SVR2、ST這3種機制的路徑持續(xù)時間制成見表4。

表4 節(jié)點數(shù)量與路徑持續(xù)時間數(shù)據(jù)

節(jié)點數(shù)目越多，找到穩(wěn)定的節(jié)點機率越高，因此以穩(wěn)定度為優(yōu)先考慮的SVR1及SVR2找到的路徑持續(xù)時間會越長。當(dāng)節(jié)點個數(shù)為50時，SVR1的路徑持續(xù)時間高于ST達91%，SVR2的路徑持續(xù)時間高于ST達86%；而在節(jié)點個數(shù)為200 時，SVR1的路徑持續(xù)時間高于ST可達93%，SVR2的路徑持續(xù)時間高于ST達88%。因此，節(jié)點數(shù)越多，SVR1、SVR2均有不錯的表現(xiàn)。如圖6所示。

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

圖7 節(jié)點移動比例與路徑持續(xù)時間關(guān)系

3.3.2 路由選擇成功率分析

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

3.3.3 路徑長度分析

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

4 結(jié)束語

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