李 繁，張曉宇，劉 繼

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

0 引 言

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

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

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

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

第一類是最短路徑路由技術(shù)[6]。此類的路徑選擇是以該路徑經(jīng)過的中繼點(diǎn)較少者為優(yōu)先考慮，例如C.E. Perkins等提出的DSDV方法，是基于傳統(tǒng)Bellman-Ford路由選擇算法改良而發(fā)展出來的。一個(gè)以路由表(routing table)為基礎(chǔ)的路由通信協(xié)議，意指每一個(gè)行動(dòng)節(jié)點(diǎn)必須儲(chǔ)存一個(gè)路由表，其中記錄所有與該節(jié)點(diǎn)可能進(jìn)行鏈接的節(jié)點(diǎn)及距離，路由表內(nèi)的每筆記錄同時(shí)也包含了一組序列號(hào)碼(sequence number)，用來判斷該筆數(shù)據(jù)的新舊情況，以避免各行動(dòng)節(jié)點(diǎn)交換路徑信息時(shí)發(fā)生拓?fù)浣Y(jié)構(gòu)改變，而產(chǎn)生“無窮計(jì)數(shù)”(count to infinity)的問題。另外，C.E. Perkins等又提出了AODV的方法。AODV 是以on-demand的路徑建立方式，不同于DSDV通過網(wǎng)絡(luò)拓?fù)錉顟B(tài)改變來驅(qū)動(dòng)路徑信息的機(jī)制，只有在需要某端點(diǎn)路徑信息的情況下，才對(duì)該端點(diǎn)進(jìn)行路徑尋找與建立的動(dòng)作，不需固定周期性的去維護(hù)路徑信息[7，8]。CGSR是建構(gòu)在DSDV之上的路由協(xié)議。CGSR的機(jī)制是將整個(gè)網(wǎng)絡(luò)劃分成數(shù)個(gè)集群(cluster)，每個(gè)集群中選出集群管理者(cluster head)，由他們來負(fù)責(zé)管理集群內(nèi)的成員和交換重要的相關(guān)信息，和記錄整個(gè)網(wǎng)絡(luò)的架構(gòu)，這種方式是以table-driven為導(dǎo)向，非集群管理的節(jié)點(diǎn)就不必記錄這些信息，如此一來，整個(gè)網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)所記錄的總數(shù)據(jù)量就可以大大的減少。TORA將鏈接方向逆轉(zhuǎn)(link reversal)的觀念運(yùn)用在Ad-Hoc無線網(wǎng)絡(luò)上，是一種分布式的路由算法，非常適合在高度動(dòng)態(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的位置信息來達(dá)到改善Ad-Hoc無線網(wǎng)絡(luò)路由選擇的效能。LAR的作法在于縮小尋找路徑時(shí)的廣播范圍，同時(shí)又不影響其路徑的找尋。首先假設(shè)每一個(gè)節(jié)點(diǎn)已知自己目前的位置，同時(shí)源節(jié)點(diǎn)知道目的節(jié)點(diǎn)在t0的位置L及目前的時(shí)間為t1并且假設(shè)源節(jié)點(diǎn)知道目的節(jié)點(diǎn)的平均速度V。有了這些信息，源節(jié)點(diǎn)可以由此推測(cè)出目的節(jié)點(diǎn)目前會(huì)在那個(gè)區(qū)域內(nèi)，因此就可以得知預(yù)測(cè)區(qū)域(Expected Zone)。畫出預(yù)測(cè)區(qū)域之后就可得知欲廣播的范圍，就是所謂的尋求區(qū)域(Request Zone)[13，14]。GRID協(xié)議通過衛(wèi)星定位系統(tǒng)將網(wǎng)絡(luò)分割成很多四方格且每個(gè)格子中選出一個(gè)靠近中心點(diǎn)的網(wǎng)關(guān)節(jié)點(diǎn)來記錄格子內(nèi)部的路由表，負(fù)責(zé)區(qū)域內(nèi)部的通信，使用table-driven的方式。當(dāng)網(wǎng)關(guān)節(jié)點(diǎn)要離開格子時(shí)就將路由表廣播給格子內(nèi)的其他成員，再由成員中選出代替的網(wǎng)關(guān)節(jié)點(diǎn)。區(qū)域之間的通信必須經(jīng)由網(wǎng)關(guān)節(jié)點(diǎn)，使用on-demand的方式，除了源主機(jī)和目的主機(jī)之外，路徑的中間點(diǎn)必為網(wǎng)關(guān)節(jié)點(diǎn)。

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

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

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

2.1 協(xié)議概要

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

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

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

(1)

(2)

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

(3)

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

(4)

(5)

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

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

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

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

(6)

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

(7)

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

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

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

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

2.3.2 路徑搜索程序

當(dāng)節(jié)點(diǎn)S欲傳送數(shù)據(jù)給節(jié)點(diǎn)D時(shí)，節(jié)點(diǎn)S會(huì)先將自己的地址及目的節(jié)點(diǎn)地址等信息存放于路徑請(qǐng)求封包中，再將該封包廣播給鄰近節(jié)點(diǎn)A、B，節(jié)點(diǎn)A、B收到該封包后判斷是否先前處理過封包，若無，則繼續(xù)廣播給鄰近節(jié)點(diǎn)，若已處理過，則直接丟棄該封包，不再繼續(xù)廣播下去。當(dāng)節(jié)點(diǎn)A收到封包時(shí)，將其ID及LSV分別儲(chǔ)存在IN及METRIC字段，如此進(jìn)行下去，每個(gè)節(jié)點(diǎn)都將自己的ID及LSV儲(chǔ)存在路徑請(qǐng)求封包中，當(dāng)目的節(jié)點(diǎn)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)定的路徑，同時(shí)也會(huì)是一條較短路徑。因此，我們所提的路徑選擇方法，不僅確保路徑的穩(wěn)定度，也不會(huì)帶來過大的通信延遲

PSV=LSV1×LSV2×…×LSVn

(8)

2.3.3 路徑回復(fù)程序

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

2.4 范 例

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

表1 節(jié)點(diǎn)A的信號(hào)方差

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

當(dāng)節(jié)點(diǎn)S需要一條到達(dá)節(jié)點(diǎn)D的路徑時(shí)，節(jié)點(diǎn)S會(huì)發(fā)出路徑請(qǐng)求封包給節(jié)點(diǎn)A、B，節(jié)點(diǎn)A收到封包，將LSV

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

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

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

3 實(shí)驗(yàn)分析

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

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

在我們的研究中，仿真環(huán)境僅限于網(wǎng)絡(luò)層(network layer)，對(duì)于數(shù)據(jù)鏈路層(data link layer)的細(xì)節(jié)，如MAC協(xié)議、多重存取所造成的干擾(multiple accessinterference)、功率下降、鏈接錯(cuò)誤(link error)，并不加以考慮。而物理層以及信道(channel)的細(xì)節(jié)問題，也不加以考慮。也就是說，兩個(gè)節(jié)點(diǎn)互相在傳輸范圍內(nèi)時(shí)，即可成功傳送數(shù)據(jù)，反之，則接收不到數(shù)據(jù)。本文之所以不考慮上述狀況，是因?yàn)橐陨蠁栴}可以用現(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

移動(dòng)主機(jī)個(gè)數(shù)：50～200個(gè)

傳輸半徑：150 m

模擬時(shí)間：100 s

移動(dòng)速度：10～50 m/sec

移動(dòng)模式：360度任意移動(dòng)

Beacon 區(qū)間：2 s

節(jié)點(diǎn)移動(dòng)比例：20～80%

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

3.3.1 穩(wěn)定度分析

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

表3 節(jié)點(diǎn)移動(dòng)速度與路徑持續(xù)時(shí)間數(shù)據(jù)

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

圖5 節(jié)點(diǎn)移動(dòng)速度與路徑持續(xù)時(shí)間關(guān)系

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

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

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

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

圖7 節(jié)點(diǎn)移動(dòng)比例與路徑持續(xù)時(shí)間關(guān)系

3.3.2 路由選擇成功率分析

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

3.3.3 路徑長(zhǎng)度分析

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

4 結(jié)束語

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