時間：2022-10-21 11:11:48
導(dǎo)語：在路由協(xié)議的撰寫旅程中，學(xué)習(xí)并吸收他人佳作的精髓是一條寶貴的路徑，好期刊匯集了九篇優(yōu)秀范文，愿這些內(nèi)容能夠啟發(fā)您的創(chuàng)作靈感，引領(lǐng)您探索更多的創(chuàng)作可能。
關(guān)鍵詞：物聯(lián)網(wǎng)；無線傳感器網(wǎng)絡(luò)；路由協(xié)議；能源利用率
中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2016）03-00-04
0 引 言
無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks， WSN）作為物聯(lián)網(wǎng)的重要組成部分，具有廣闊的應(yīng)用前景[1]。傳統(tǒng)網(wǎng)絡(luò)主要應(yīng)用于用戶間的數(shù)據(jù)通信和資源共享， 相比之下，WSN應(yīng)用范圍更加廣泛，例如環(huán)境監(jiān)測、敵情偵查等。對于WSN路由協(xié)議，應(yīng)用場景的不同會導(dǎo)致它們之間存在某些差異。本文主要從原理、特點(diǎn)以及優(yōu)缺點(diǎn)三個方面對目前具有代表性的WSN路由協(xié)議進(jìn)行分析，并對其特性進(jìn)行歸納總結(jié)。
根據(jù)WSN中傳感器節(jié)點(diǎn)的特性以及節(jié)點(diǎn)間數(shù)據(jù)傳輸?shù)奶卣?，可以將WSN路由協(xié)議分為以數(shù)據(jù)為中心的路由、層次路由、地理位置路由以及基于網(wǎng)絡(luò)流量和服務(wù)質(zhì)量的路由[2]。
1 以數(shù)據(jù)為中心的路由
傳統(tǒng)網(wǎng)絡(luò)中的路由協(xié)議通常是通過地址找到相對應(yīng)的資源，即以地址為中心；而對于WSN，傳感器節(jié)點(diǎn)的部署卻無規(guī)律。在這種情況下，節(jié)點(diǎn)的具體編號對用戶來說并不重要，用戶只需要得到融合后的、有價(jià)值的數(shù)據(jù)即可，即WSN主要以數(shù)據(jù)為中心。以數(shù)據(jù)為中心的路由協(xié)議包括Flooding、Gossiping、SPIN、Directed Diffusion和Rumor。
1.1 Flooding路由協(xié)議
Flooding協(xié)議（洪泛路由協(xié)議）是一種傳統(tǒng)的廣播式路由協(xié)議[3]。當(dāng)環(huán)境中的某一傳感器節(jié)點(diǎn)監(jiān)測或接收到數(shù)據(jù)時，無條件的將數(shù)據(jù)轉(zhuǎn)發(fā)給自己的鄰居節(jié)點(diǎn)。Flooding協(xié)議原理如圖1所示。
Flooding協(xié)議最突出的特點(diǎn)在于節(jié)點(diǎn)對數(shù)據(jù)進(jìn)行“無條件轉(zhuǎn)發(fā)”，直到數(shù)據(jù)傳遍整個網(wǎng)絡(luò)或是達(dá)到規(guī)定的跳數(shù)上限為止。這一特點(diǎn)使得該協(xié)議容易實(shí)現(xiàn)，并且能較好地適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的改變。因此，它具有較強(qiáng)的魯棒性，可以應(yīng)用于軍事領(lǐng)域或者惡劣環(huán)境。但該特點(diǎn)也給Flooding協(xié)議帶來了一個致命的弱點(diǎn)，即信息爆炸問題。圖1中同一個數(shù)據(jù)包被3次發(fā)送給E節(jié)點(diǎn)，這對于E節(jié)點(diǎn)來說，極大地浪費(fèi)了能量。圖2所示為其重疊問題示意圖，其中深色部分為A、B節(jié)點(diǎn)所能感知到的區(qū)域的重疊部分，如果重疊區(qū)域有事件發(fā)生，那么該事件信息將被發(fā)送給C節(jié)點(diǎn)兩次。重疊問題普遍存在而且很難避免，并且會隨著節(jié)點(diǎn)分布密集程度的增大而變得愈發(fā)嚴(yán)重。
目前來講，F(xiàn)looding協(xié)議過于浪費(fèi)網(wǎng)絡(luò)資源和節(jié)點(diǎn)能量，因此很少被直接運(yùn)用，一般將其作為衡量標(biāo)準(zhǔn)去評價(jià)其他路由算法。
1.2 Gossiping路由協(xié)議
Gossiping協(xié)議在Flooding協(xié)議的基礎(chǔ)上演變而來。改進(jìn)之處在于數(shù)據(jù)包被隨機(jī)轉(zhuǎn)發(fā)給某幾個相鄰節(jié)點(diǎn)，并非所有相鄰節(jié)點(diǎn)，這可以在一定程度上控制信息內(nèi)爆問題。但是由于節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包時隨機(jī)選取的相鄰節(jié)點(diǎn)可能并不是所有相鄰節(jié)點(diǎn)里面距離該節(jié)點(diǎn)較近的幾個點(diǎn)，很可能使得數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)的時延增大，或是出現(xiàn)跳數(shù)已達(dá)最大但數(shù)據(jù)仍未傳送到目的節(jié)點(diǎn)所導(dǎo)致的信息傳送失敗問題。
1.3 SPIN路由協(xié)議
SPIN（Sensor Protocol for Information via Negotiation）協(xié)議基于Flooding協(xié)議，改進(jìn)之處在于節(jié)點(diǎn)之間通過協(xié)商（Negotiation）的方式緩解數(shù)據(jù)冗余問題。該協(xié)議包含以下三種數(shù)據(jù)包類型： 消息廣播包（ADV）、 數(shù)據(jù)請求包（REQ）和數(shù)據(jù)包（DATA）。
圖3所示為SPIN協(xié)議原理，其中S節(jié)點(diǎn)有新數(shù)據(jù)時則向其所有相鄰節(jié)點(diǎn)ADV消息，假設(shè)A和C有該數(shù)據(jù)，則它們不回復(fù)給S任何消息；假設(shè)B沒有該數(shù)據(jù)，則B需要回復(fù)REQ數(shù)據(jù)包，S收到REQ數(shù)據(jù)包后將原始數(shù)據(jù)DATA發(fā)送給B節(jié)點(diǎn)。B接收到DATA后與自己的數(shù)據(jù)進(jìn)行融合并對B的相鄰節(jié)點(diǎn)重復(fù)該過程。
該路由協(xié)議的核心基于元數(shù)據(jù)（Metadata）的協(xié)商（Negotiation）過程。協(xié)議中采用“三次握手”機(jī)制，即節(jié)點(diǎn)只對回復(fù)REQ信息的節(jié)點(diǎn)發(fā)送原始數(shù)據(jù)，這相比給所有相鄰節(jié)點(diǎn)發(fā)送原始數(shù)據(jù)而言，大大減少了冗余數(shù)據(jù)的傳輸。
該協(xié)議仍然有一些不足之處。若某一個節(jié)點(diǎn)收到多個相鄰節(jié)點(diǎn)的REQ消息，這時需采用“退避算法”，該方法可能會增加時延，也可能會有某些節(jié)點(diǎn)對許多消息都“感興趣”，那么它將接收大量數(shù)據(jù)，這些節(jié)點(diǎn)的能量容易耗盡。
1.4 DD路由協(xié)議
DD協(xié)議（Directed Diffusion定向擴(kuò)散路由協(xié)議）中路徑的建立過程需要經(jīng)歷以下三個階段：
（1）“興趣擴(kuò)散”階段，匯聚節(jié)點(diǎn)（Sink）采用周期性洪泛方式廣播自己的“興趣”，即自己要接收何種類型的消息；
（2）“梯度建立”階段，興趣擴(kuò)散路徑即為數(shù)據(jù)傳輸路徑，只是傳輸方向相反；
（3）“強(qiáng)化路徑”階段，即從“梯度建立”階段所得到的路徑中選取合適路徑進(jìn)行數(shù)據(jù)傳輸。
DD協(xié)議實(shí)現(xiàn)過程如圖4所示。
當(dāng)加強(qiáng)路徑中的某一段出現(xiàn)故障時，原加強(qiáng)路徑上的節(jié)點(diǎn)會啟動新的加強(qiáng)過程，從而建立新的加強(qiáng)路徑。“加強(qiáng)路徑”的修復(fù)如圖5所示。
DD協(xié)議中路徑加強(qiáng)機(jī)制可以顯著提高數(shù)據(jù)的傳輸速率，但加強(qiáng)路徑上的節(jié)點(diǎn)會消耗大量能量，為了確保能量均衡消耗，需要周期性替換加強(qiáng)路徑，這將增加網(wǎng)絡(luò)維護(hù)的難度。當(dāng)某一加強(qiáng)路徑出現(xiàn)故障并且暫未更新加強(qiáng)路徑時，多次失敗的發(fā)送過程也會增大端到端時延并耗費(fèi)部分節(jié)點(diǎn)的能量[4]。
1.5 Rumor路由協(xié)議
對于某些節(jié)點(diǎn)較少、需要傳輸?shù)臄?shù)據(jù)量較少或是已知事件發(fā)生區(qū)域的WSN來說，運(yùn)用上面提及的幾種路由協(xié)議將會帶來一些不必要的開銷。Rumor協(xié)議（謠傳路由協(xié)議）能夠在一定程度上緩解這種問題，減少網(wǎng)絡(luò)中的冗余數(shù)據(jù)量。該協(xié)議中引入（Agent）消息概念，消息由感知到信息的傳感器節(jié)點(diǎn)產(chǎn)生[5]。Sink節(jié)點(diǎn)產(chǎn)生查詢消息、源節(jié)點(diǎn)產(chǎn)生消息，兩者均在網(wǎng)絡(luò)中隨機(jī)傳播，到兩者傳播路徑出現(xiàn)交點(diǎn)為止，即構(gòu)成一條完整的數(shù)據(jù)傳輸路徑。Rumor路由協(xié)議原理如圖6所示，實(shí)線為消息傳播路徑，虛線為查詢消息傳播路徑，兩條路徑在B點(diǎn)處會合，從而形成一條完整的傳輸線路。
Rumor協(xié)議使用單播隨機(jī)轉(zhuǎn)發(fā)方式能夠在一定程度上減少網(wǎng)絡(luò)的開銷，但由于每個傳感器節(jié)點(diǎn)需要維護(hù)的列表數(shù)目增加了，維護(hù)的難度也就增大了。協(xié)議中采用的隨機(jī)轉(zhuǎn)發(fā)方式無法保證數(shù)據(jù)傳輸?shù)穆窂绞亲疃搪窂剑虼藷o法保證數(shù)據(jù)傳輸?shù)臅r效性，并且容易出現(xiàn)環(huán)路。
2 層次路由
層次路由也叫集群結(jié)構(gòu)路由，它通過引入簇的概念實(shí)現(xiàn)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的分層管理。簇頭和簇成員各司其職，共同完成數(shù)據(jù)的傳輸。
2.1 LEACH協(xié)議
LEACH協(xié)議（Low-energy Adaptive Clustering Hierarchy，低功耗自適應(yīng)集簇分層型協(xié)議）通過特定的簇頭選舉算法確定哪些節(jié)點(diǎn)為某一個特定周期內(nèi)的簇頭，簇頭通過廣播方式告知其它節(jié)點(diǎn)自己是簇頭。非簇頭節(jié)點(diǎn)選擇加入某個簇之后，會被分配固定的時間片用于發(fā)送消息，簇頭負(fù)責(zé)對后續(xù)的消息發(fā)送過程進(jìn)行管理。
該協(xié)議通過對傳感器節(jié)點(diǎn)的分層管理，優(yōu)化網(wǎng)絡(luò)體系結(jié)構(gòu)，并且利用簇頭節(jié)點(diǎn)的信息融合能力減少網(wǎng)絡(luò)中的冗余數(shù)據(jù)。不足之處在于，通過簇頭選舉算法選舉產(chǎn)生的多個簇頭并不一定能夠遍及整個網(wǎng)絡(luò)，因此可能導(dǎo)致某些節(jié)點(diǎn)無法接收和發(fā)送數(shù)據(jù)。
2.2 TTDD路由協(xié)議
TTDD協(xié)議（Two-Tier Data Dissemination）相比其他WSN路由協(xié)議而言可以很好地處理Sink節(jié)點(diǎn)移動問題。傳輸數(shù)據(jù)前先以源節(jié)點(diǎn)為中心建立網(wǎng)格，最接近網(wǎng)格交叉點(diǎn)的節(jié)點(diǎn)負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)。Sink節(jié)點(diǎn)在其所處網(wǎng)格區(qū)間通過洪泛方式發(fā)起查詢請求，距離Sink節(jié)點(diǎn)最近的轉(zhuǎn)發(fā)節(jié)點(diǎn)作為直接轉(zhuǎn)發(fā)節(jié)點(diǎn)并向其上游節(jié)點(diǎn)傳送查詢消息，直到查詢消息傳送到源節(jié)點(diǎn)為止。查詢消息走過的路徑即為數(shù)據(jù)傳輸路徑，但兩者傳送方向相反。該協(xié)議中定義了初級（PA）和直接（IA），以便Sink節(jié)點(diǎn)在等待數(shù)據(jù)時可以繼續(xù)移動。
TTDD適用于節(jié)點(diǎn)分布較為密集的網(wǎng)絡(luò)，機(jī)制的存在使得Sink節(jié)點(diǎn)即使是在等待查詢數(shù)據(jù)時仍然可以繼續(xù)移動，這更貼近實(shí)際的網(wǎng)絡(luò)環(huán)境。但網(wǎng)格尺寸的確定對整個算法的效率來講影響較大，因此劃分合適大小的網(wǎng)格對于該算法來講較為重要。
3 地理位置路由
對于WSN網(wǎng)絡(luò)來講，短距離、少跳數(shù)的傳輸通常情況下能夠縮短傳播時延并節(jié)省能量[6]。節(jié)點(diǎn)可以利用一些地理位置信息選擇合適的發(fā)送路徑，從而提高網(wǎng)絡(luò)性能。地理位置路由協(xié)議主要包括GPSR協(xié)議和GEAR協(xié)議。
3.1 GPSR路由協(xié)議
GPSR協(xié)議（Greedy Perimeter Stateless Routing）要求節(jié)點(diǎn)知道自己的地理位置，想要發(fā)送數(shù)據(jù)的節(jié)點(diǎn)利用貪婪算法選取轉(zhuǎn)發(fā)節(jié)點(diǎn)。
貪婪算法的示意圖如圖7所示，B節(jié)點(diǎn)有數(shù)據(jù)需要發(fā)送，B的鄰居節(jié)點(diǎn)C比B節(jié)點(diǎn)離目的節(jié)點(diǎn)A更近，因此B將數(shù)據(jù)轉(zhuǎn)發(fā)給C。C再根據(jù)貪婪算法重復(fù)此過程，當(dāng)數(shù)據(jù)包傳送到目的節(jié)點(diǎn)A時此次傳送過程才結(jié)束。由圖7貪婪算法示意圖不難發(fā)現(xiàn)， B-C-D-E-A的傳送距離比實(shí)線標(biāo)出的線路更短，但是由于F點(diǎn)相比E點(diǎn)距離D點(diǎn)更近，因此D點(diǎn)選擇把數(shù)據(jù)發(fā)送給F點(diǎn)。貪婪算法所產(chǎn)生的“局部優(yōu)化”問題，可能會增加數(shù)據(jù)的傳播時延。
GPSR協(xié)議中不需要花費(fèi)大量精力去維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，它既能支持靜態(tài)WSN，又能支持動態(tài)WSN。但貪婪算法的使用可能導(dǎo)致協(xié)議實(shí)現(xiàn)過程中出現(xiàn)路由空洞問題，這時需要采用其他算法以達(dá)到整個路由算法收斂的目的，因而會在一定程度上增加傳播時延[7]。
3.2 GEAR協(xié)議
GEAR協(xié)議（Geographic and Energy Aware Routing）與GPSR協(xié)議都需要將目標(biāo)區(qū)域分割成若干個子區(qū)域，但GEAR協(xié)議中消息是向子區(qū)域的中心位置發(fā)送。GEAR協(xié)議與GPSR協(xié)議不同之處在于，節(jié)點(diǎn)需要知道自身剩余能量，并根據(jù)位置和剩余能量兩個要素按照一定權(quán)重計(jì)算代價(jià)。代價(jià)計(jì)算見公式（1）所示：
估計(jì)：F（Ni，R）=α?D（Ni，R）+（1-α）?LE（Ni）
實(shí)際：F（Ni，R）=α?EC（Ni，R）+（1-α）?LE（Ni） （1）
說明：Ni為具有轉(zhuǎn)發(fā)需求節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，R為目標(biāo)區(qū)域的中心位置。若N不知道Ni的實(shí)際代價(jià)時使用估計(jì)代價(jià)。D（Ni， R）代表Ni和R的距離； LE（Ni）表示Ni的剩余能量；EC（Ni，R）表示Ni到R的能量損耗；α代表權(quán)重。
GEAR協(xié)議利用位置信息避免了查詢消息的內(nèi)爆問題，同時它在選擇轉(zhuǎn)發(fā)路徑時考慮了節(jié)點(diǎn)到達(dá)指定區(qū)域的代價(jià)，這其中涉及消息傳送過程消耗的能量以及節(jié)點(diǎn)剩余能量，以此達(dá)到均衡消息的目的。但由于使用了貪婪算法，該協(xié)議在實(shí)現(xiàn)過程中較容易出現(xiàn)路由空洞問題。
4 基于網(wǎng)絡(luò)流量和服務(wù)質(zhì)量的路由
對于WSN這個特殊的網(wǎng)絡(luò)，傳輸路徑的選擇需要參考網(wǎng)絡(luò)流量或是QoS性能指標(biāo)，這時需要使用基于網(wǎng)絡(luò)流量和服務(wù)質(zhì)量的路由協(xié)議。例如基于QoS的SAR協(xié)議和SPEED協(xié)議。
4.1 SAR協(xié)議
SAR協(xié)議（Sequential Assignment Routing）是首個在WSN中做到保證網(wǎng)絡(luò)服務(wù)質(zhì)量的路由協(xié)議[8]。在該協(xié)議中，Sink節(jié)點(diǎn)的所有一跳鄰居節(jié)點(diǎn)都以它為根創(chuàng)建生成樹，見圖8第一部分；其他節(jié)點(diǎn)重復(fù)此過程，多個生成樹的疊加可以得到圖8中第二部分。在路徑匯總圖中，有多條可達(dá)Sink節(jié)點(diǎn)且具有不同QoS參數(shù)的路徑可供選擇。節(jié)點(diǎn)發(fā)送數(shù)據(jù)時，按照QoS以及能量剩余情況選擇合適路徑進(jìn)行傳輸。
SAR協(xié)議在保證QoS的基礎(chǔ)上，通過維護(hù)傳感器節(jié)點(diǎn)和Sink節(jié)點(diǎn)間的多條路徑，使得某個節(jié)點(diǎn)或某條路徑出現(xiàn)故障時，網(wǎng)絡(luò)仍可以正常運(yùn)行，從而增強(qiáng)網(wǎng)絡(luò)的健壯性。不足之處在于節(jié)點(diǎn)需存儲大量冗余路由信息，不僅浪費(fèi)資源還導(dǎo)致路由信息維護(hù)的難度增大。
4.2 SPEED協(xié)議
SPEED協(xié)議是一種QoS協(xié)議，它通過設(shè)定一個速度門限對下一跳節(jié)點(diǎn)進(jìn)行挑選，實(shí)現(xiàn)擁塞控制功能[8]。當(dāng)節(jié)點(diǎn)準(zhǔn)備發(fā)送數(shù)據(jù)包時，通過節(jié)點(diǎn)自身、鄰居節(jié)點(diǎn)和目的節(jié)點(diǎn)三者的距離關(guān)系劃分出一個轉(zhuǎn)發(fā)結(jié)點(diǎn)候選集合，選取轉(zhuǎn)發(fā)速度高于規(guī)定的門限值的節(jié)點(diǎn)構(gòu)成轉(zhuǎn)發(fā)節(jié)點(diǎn)集合。如果轉(zhuǎn)發(fā)節(jié)點(diǎn)集合為空，可以通過調(diào)整門限值重新選取。
協(xié)議中對鄰居節(jié)點(diǎn)的篩選過程，有利于保證傳輸?shù)膶?shí)時性，并使整個網(wǎng)絡(luò)的傳輸負(fù)荷處于動態(tài)平衡狀態(tài)，調(diào)節(jié)節(jié)點(diǎn)的能量消耗[9]。因SPEED協(xié)議同時也是與地理位置相關(guān)的路由協(xié)議并使用了貪婪算法，因此很難避免路由空洞問題[10]。
5 結(jié) 語
本文主要針對目前存在的典型WSN路由協(xié)議，從原理、特點(diǎn)和優(yōu)缺點(diǎn)進(jìn)行分析，以便為日后的WSN路由協(xié)議研究提供一些參考。
參考文獻(xiàn)
[1]周雅琴，譚定忠.無線傳感器網(wǎng)絡(luò)應(yīng)用及研究現(xiàn)狀[J]. 傳感器世界， 2009，5（5）：35-40.
[2]畢俊蕾.基于分簇的WSN路由算法的研究與設(shè)計(jì)[D].開封：河南大學(xué)，2008.
[3]黃化吉，馮穗力，秦麗姣，等.NS網(wǎng)絡(luò)模擬和協(xié)議仿真[M].北京：人民郵電出版社，2010.
[4]彭海英，唐伶俐，唐紅.無線傳感器網(wǎng)絡(luò)中DD 路由協(xié)議的改進(jìn)研究[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（14）：127-130.
[5]夏靜，莊雷，白雨.無線傳感器網(wǎng)絡(luò)謠傳路由研究及改進(jìn)[J].微計(jì)算機(jī)信息（測控自動化），2007，23（7-1）：152-153.
[6]顧一中.無線傳感器網(wǎng)絡(luò)地理位置路由相關(guān)技術(shù)研究[D].南京：南京理工大學(xué)，2008.
[7]唐國明，謝羿，唐九陽，等.一種基于左、右手法則的GPSR分區(qū)邊界轉(zhuǎn)發(fā)路由協(xié)議[J].計(jì)算機(jī)應(yīng)用研究， 2011，28（3）：1099-1101.
[8]趙強(qiáng)利，蔣艷凰，徐明.無線傳感器網(wǎng)絡(luò)路由協(xié)議的分析與比較[J].計(jì)算機(jī)科學(xué)， 2009，36（2）：35-41.
關(guān)鍵詞： 動態(tài)路由；OSPF；自治系統(tǒng)配置命令；鏈路
中圖分類號：TP3 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）34-7697-02
21世紀(jì)是網(wǎng)絡(luò)的世界，我們每個人都在不知不覺中融入這個網(wǎng)絡(luò)世界。而路由器在網(wǎng)絡(luò)中發(fā)揮著越來越重要的作用，其主要負(fù)責(zé)在網(wǎng)絡(luò)層間按傳輸數(shù)據(jù)分組的，并確定網(wǎng)絡(luò)上數(shù)據(jù)傳送的最佳路徑。世界各地的個人和企業(yè)單位接入到Internet的自治系統(tǒng)有大有小，小型自治系統(tǒng)因其網(wǎng)絡(luò)結(jié)構(gòu)簡單往往采用靜態(tài)路由技術(shù)即可完成自治系統(tǒng)內(nèi)的路由尋址，然而大、中型自治系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)往往更加復(fù)雜，采用依靠人工分配的靜態(tài)路由技術(shù)存在很大的困難，因此根據(jù)合理的路由尋址算法設(shè)計(jì)的動態(tài)路由技術(shù)隨之誕生，而OSPF動態(tài)路由技術(shù)因其功能強(qiáng)大、可拓展性強(qiáng)和網(wǎng)絡(luò)性能優(yōu)越在動態(tài)路由技術(shù)中格外優(yōu)秀，被廣泛應(yīng)用于各大、中型自治系統(tǒng)中。
1 OSPF的基本概念
開放最短路徑優(yōu)先協(xié)議（Open Shortest Path First）簡稱OSPF，它是路由選擇協(xié)議中非常重要的一種協(xié)議，這是一種典型的鏈路狀態(tài)（Link-state）路由協(xié)議，是由Internet工程任務(wù)組開發(fā)的內(nèi)部網(wǎng)關(guān)（IGP）路由協(xié)議，其主要用在一個路由域內(nèi)。路由域是指一個網(wǎng)絡(luò)自治系統(tǒng)（Autonomous System），所謂自治系統(tǒng)是指一組路由器都使用同一種路由協(xié)議交換路由信息，網(wǎng)絡(luò)中每個路由器都有一個唯一的標(biāo)識，用于在鏈路狀態(tài)數(shù)據(jù)庫（LSDB）中標(biāo)識自己。LSDB描述的是整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，包括網(wǎng)絡(luò)內(nèi)所有的路由器，作為一種鏈路狀態(tài)的路由協(xié)議，OSPF將鏈路狀態(tài)廣播數(shù)據(jù)包LSA（Link State Advertisement）傳送給在某一區(qū)域內(nèi)的所有路由器，OSPF協(xié)議使用最短路徑優(yōu)先算法，利用LSA通告得來的信息計(jì)算每一個目標(biāo)網(wǎng)絡(luò)的最短路徑，以自身為根生成一個樹，包含了到達(dá)每個目的網(wǎng)絡(luò)的完整路徑。
OSPF的路由標(biāo)示是一個32位的數(shù)字，它在自治系統(tǒng)中被用來唯一識別路由器。默認(rèn)地使用最高回送地址，若回送地址沒有被配置，則使用物理接口上最高的IP地址作為路由標(biāo)示。OSPF在相鄰路由器間建立鄰接關(guān)系，使它們能利用HELLO包維護(hù)關(guān)系并交換信息。OSPF使用區(qū)域來為自治系統(tǒng)分段，區(qū)域0是一個主干區(qū)域，每一個OSPF網(wǎng)絡(luò)必須具有，其他的區(qū)域通過區(qū)域0互連到一起。
2 OSPF的特點(diǎn)
OSPF路由協(xié)議主要用在大型自治系統(tǒng)內(nèi)，這是一種鏈路狀態(tài)的路由協(xié)議，，而距離矢量路由協(xié)議RIP（Routing Information Protocol）則主要用在小型自治系統(tǒng)內(nèi)，兩個路由協(xié)議都具有重要的作用，RIP作為靜態(tài)路由協(xié)議，具有適于小型網(wǎng)絡(luò)，管理員可手工配置，精確控制路由選擇，改進(jìn)網(wǎng)絡(luò)性能等優(yōu)點(diǎn)，但它特別不適合于大型網(wǎng)絡(luò)自治系統(tǒng)。而OSPF路由協(xié)議與RIP相比，具有如下優(yōu)點(diǎn)：1、RIP路由協(xié)議中用跳（HOP）來表示到達(dá)目的網(wǎng)絡(luò)所要經(jīng)過的路由器個數(shù)，RIP跳數(shù)最高為15，超過15跳的路由被認(rèn)為不可達(dá)，而OSPF不受路由跳數(shù)的限制，它只受限于帶寬和網(wǎng)絡(luò)延遲，因而OSPF更適合應(yīng)用于大型網(wǎng)絡(luò)中。2、RIP在規(guī)劃網(wǎng)絡(luò)時是不支持可變長子網(wǎng)掩碼（VLSM），這將導(dǎo)致IP地址分配的低效率，而OSPF路由協(xié)議支持VLSM，現(xiàn)在IPV4資源短缺，我們在劃分大型網(wǎng)絡(luò)的子網(wǎng)時，往往采用VLSM，這樣劃分子網(wǎng)效率更高，更節(jié)約IP資源，所以O(shè)SPF更適合大型網(wǎng)絡(luò)。3、RIP必須每30秒就要周期性的廣播整個路由表，才能使網(wǎng)絡(luò)運(yùn)行正常，如果RIP用在大型網(wǎng)絡(luò)中，它會產(chǎn)生很多廣播信息，而這些廣播會占用較多的網(wǎng)絡(luò)帶寬資源，較頻繁的更新有可能導(dǎo)致網(wǎng)絡(luò)擁塞，其結(jié)果就是RIP用在大型網(wǎng)絡(luò)中收斂速度較慢，甚至無法收斂。而OSPF使用組播發(fā)送鏈路狀態(tài)更新，在鏈路狀態(tài)變化時才進(jìn)行更新，這樣提高了帶寬的利用率， 收斂速度也大幅提高，能夠在最短的時間內(nèi)將路由變化傳遞到整個自治系統(tǒng)。4、RIP沒有網(wǎng)絡(luò)延遲和鏈路開銷的概念，擁有較少跳數(shù)的路由總是被選為最佳路由，即使較長的路徑有低的延遲和開銷，并且RIP沒有區(qū)域的概念，不能在任意比特位進(jìn)行路由匯總。而在OSPF路由協(xié)議中，往往把一個路由域劃分為很多個區(qū)域area，每一個區(qū)域都通過OSPF邊界路由器相連，區(qū)域間可以通過路由總結(jié)（Summary）來減少路由信息，從而減小路由表，提高路由器的運(yùn)算速度。
OSPF路由協(xié)議擁有很多優(yōu)點(diǎn)，特別適合用于大型網(wǎng)絡(luò)，提高網(wǎng)絡(luò)的運(yùn)行速度，但它也有缺點(diǎn)：①使用OSPF路由協(xié)議，需要網(wǎng)絡(luò)管理員事前先進(jìn)行區(qū)域規(guī)劃和路由器各端口IP屬性的設(shè)置，所以配置相對于靜態(tài)路由RIP來說顯得較為復(fù)雜，對網(wǎng)絡(luò)管理員的網(wǎng)絡(luò)知識水平要求較高。②對路由器的CPU及內(nèi)存要求較高。
3 OSPF配置命令及配置實(shí)例
在思科路由器中配置OSPF路由協(xié)議主要使用以下命令：①route ospf 進(jìn)程號，其中進(jìn)程號要求范圍為1～65535，進(jìn)程號只在路由器內(nèi)部起作用，不同路由器的進(jìn)程號可以不同。②network address 子網(wǎng)掩碼的反碼 area 區(qū)域號，區(qū)域號要求在0～4294967295內(nèi)的十進(jìn)制數(shù)，也可以是帶有IP地址格式的X.X.X.X，當(dāng)網(wǎng)絡(luò)區(qū)域號為0時或0.0.0.0時為主干域，不同網(wǎng)絡(luò)區(qū)域的路由器通過主干域?qū)W習(xí)路由信息。③show ip route，查看路由信息表，④show ip route ospf 查看OSPF協(xié)議路由信息。
某學(xué)校采用四臺思科3550路由器把整個學(xué)校劃分為3個區(qū)域，四臺路由器通過使用OSPF協(xié)議實(shí)現(xiàn)互通。路由器R1的S0端口IP為192.200.10.5/30，E0端口IP為192.1.0.129/26；路由器R2的S0端口IP為192.200.10.6/30，E0端口IP為192.1.0.65/26；路由器R3的E0端口IP為192.1.0.130/26；路由器R4的E0端口IP為192.1.0.66/26。R1的S0端口和R2的S0端口劃入?yún)^(qū)域0；R1的E0端口和R3的E0端口劃入?yún)^(qū)域1；R2的E0端口和R4的E0端口劃入?yún)^(qū)域2。各路由器配置如下：
R1：
interface Ethernet 0
ip address 192.1.0.129 255.255.255.192
interface serial 0
ip address 192.200.10.5 255.255.255.252
route ospf 500
network 192.200.10.4 0.0.0.3 area 0
network 192.1.0.128 0.0.0.63 area 1
R2：
interface Ethernet 0
ip address 192.1.0.65 255.255.255.192
interface serial 0
ip address 192.200.10.6 255.255.255.252
route ospf 600
network 192.200.10.4 0.0.0.3 area 0
network 192.1.0.64 0.0.0.63 area 2
R3：
interface Ethernet 0
ip address 192.1.0.130 255.255.255.192
route ospf 700
network 192.1.0.128 0.0.0.63 area 1
R4：
interface Ethernet 0
ip address 192.1.0.66 255.255.255.192
route ospf 800
network 192.1.0.64 0.0.0.63 area 2
在上述配置中首先對每臺路由器接口進(jìn)行配置，接口配置完后可以使用router ospf 100命令啟動一個OSPF路由選擇協(xié)議進(jìn)程，期中“100”為進(jìn)程號，每臺路由器進(jìn)程號可不同，最后使用network將相應(yīng)的網(wǎng)段加入OSPF路由進(jìn)程中，則此接口所對應(yīng)的網(wǎng)段就加入到OSPF進(jìn)程中。
綜上所述，OSPF作為一種鏈路狀態(tài)的路由協(xié)議，具有收斂快，支持變長網(wǎng)絡(luò)掩碼，支持CIDR，配置命令簡單易學(xué)等。所以在大型或復(fù)雜網(wǎng)絡(luò)中應(yīng)用OSPF協(xié)議可以極大的提高網(wǎng)絡(luò)的運(yùn)行效率。
參考文獻(xiàn)：
[1] 謝希仁.計(jì)算機(jī)網(wǎng)絡(luò)[M].5版.北京：電子工業(yè)出版社，2008
[2] 思科網(wǎng)絡(luò)技術(shù)學(xué)院.思科網(wǎng)絡(luò)技術(shù)學(xué)院教程.
[3] 思科網(wǎng)絡(luò)技術(shù)學(xué)院.思科網(wǎng)絡(luò)技術(shù)學(xué)院教程（第三，四學(xué)期）.
關(guān)鍵詞：傳感器節(jié)點(diǎn)
匯聚節(jié)點(diǎn) 能量 簇頭 路由協(xié)議
中圖分類號：TP316.4
文獻(xiàn)標(biāo)識碼：
A
文章編號：1002-2422(2010)03-0002-03
1WSN路由協(xié)議介紹
1，1協(xié)議分類
劃分路由協(xié)議種類有不同的標(biāo)準(zhǔn)。按是否需要外界輔助的地理信息準(zhǔn)則，可劃分為基于地理位置信息的協(xié)議和非基于地理位置信息的協(xié)議；按照網(wǎng)絡(luò)中數(shù)據(jù)發(fā)送模式，路由機(jī)制可以相應(yīng)地采用適合周期性地發(fā)送數(shù)據(jù)連續(xù)模式、事件驅(qū)動模式、請求驅(qū)動模式、事件驅(qū)動和請求驅(qū)動混合模式的協(xié)議；按照網(wǎng)絡(luò)路由是否動態(tài)生成，可劃分為表驅(qū)動路由協(xié)議和按需路由協(xié)議等。
下面介紹各個協(xié)議的工作方式。
SPIN采用廣告、請求、數(shù)據(jù)三種消息類型。節(jié)點(diǎn)A在發(fā)送DATA數(shù)據(jù)包之前，會對外采用泛洪方式廣播ADV包，若某個節(jié)點(diǎn)B希望接受要傳來的數(shù)據(jù)，向A回復(fù)BEQ數(shù)據(jù)包。A將向B發(fā)送數(shù)據(jù)包。
GPsR對節(jié)點(diǎn)位置進(jìn)行了統(tǒng)一編址。選擇鄰居節(jié)點(diǎn)中離數(shù)據(jù)包目的節(jié)點(diǎn)更近的點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。當(dāng)數(shù)據(jù)到達(dá)沒有比當(dāng)前節(jié)點(diǎn)更接近目的節(jié)點(diǎn)的區(qū)域(空洞)，數(shù)據(jù)無法傳輸?？衫闷矫鎴D解決空洞問題。
DIRECTED DIFFUSION路由過程分為請求、梯度建立和路徑加強(qiáng)三階段。請求含有目標(biāo)區(qū)域、數(shù)據(jù)發(fā)送速率等參數(shù)。節(jié)點(diǎn)接收到請求后，若當(dāng)前請求緩存中沒有相同的請求記錄，加入新記錄。記錄中包含了相鄰節(jié)點(diǎn)數(shù)據(jù)發(fā)送率，稱“梯度”。當(dāng)請求擴(kuò)散整個網(wǎng)絡(luò)后，選擇“梯度”最大的路徑將反向把數(shù)據(jù)快速路由。模擬過程如圖1所示。
GEAR發(fā)出請求后，數(shù)據(jù)擴(kuò)散過程包括目標(biāo)域傳送和域內(nèi)傳送。若在目標(biāo)區(qū)域傳輸遇到空洞現(xiàn)象，則根據(jù)開銷函數(shù)選擇開銷最小的鄰居作為下一跳節(jié)點(diǎn)。在域內(nèi)傳送階段，主要是通過兩種方式(泛洪、區(qū)域遞歸)使數(shù)據(jù)在域內(nèi)擴(kuò)散。
LEACH隨機(jī)選擇簇頭，普通節(jié)點(diǎn)按接收到信號強(qiáng)弱加入簇層。簇層內(nèi)節(jié)點(diǎn)單跳與簇頭通訊，簇頭與匯聚節(jié)點(diǎn)通訊。TEEN劃分出多級簇層結(jié)構(gòu)。子簇頭單跳和父簇頭通訊。PEGASIS在網(wǎng)絡(luò)中節(jié)點(diǎn)中采用算法構(gòu)造一個數(shù)據(jù)鏈，各個節(jié)點(diǎn)向靠近唯一網(wǎng)絡(luò)簇頭的鄰居發(fā)送、接收其他節(jié)點(diǎn)傳來的數(shù)據(jù)。
1，2路由協(xié)議決策要考慮的準(zhǔn)則
設(shè)計(jì)協(xié)議要考慮多種因素，包括數(shù)據(jù)通訊量、帶寬、網(wǎng)絡(luò)負(fù)載情況、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化、網(wǎng)絡(luò)節(jié)點(diǎn)增加、數(shù)據(jù)融合、可靠性等。圖2中，數(shù)據(jù)從A傳送到節(jié)點(diǎn)c。若要求傳送及時，路由可采用A－B－C路徑，減少了傳送中繼節(jié)點(diǎn)；若要求以負(fù)載平衡達(dá)到節(jié)能目的，路由應(yīng)該根據(jù)實(shí)際負(fù)載情況采用負(fù)載相對較小的路徑；若要求對不同節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行融合，可以選擇A－E－F－G－H－C融合更多節(jié)點(diǎn)的數(shù)據(jù)；若要求可靠性，路由可以同時選擇這兩條路徑。若被監(jiān)測區(qū)域內(nèi)的節(jié)點(diǎn)位置發(fā)生無規(guī)律變化。路由應(yīng)該具備適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷發(fā)生變化的能力；若要采集詳盡數(shù)據(jù)而添加節(jié)點(diǎn)，協(xié)議還應(yīng)具備支持更多節(jié)點(diǎn)協(xié)同工作的能力。
1，3路由協(xié)議的性能參數(shù)
(1)數(shù)據(jù)通訊量
把一塊數(shù)據(jù)路由到觀察者，不同算法會使得該數(shù)據(jù)的通訊量大小不一致。協(xié)議會在不同的程度上產(chǎn)生該數(shù)據(jù)塊副本。通訊量越大，網(wǎng)絡(luò)能耗越大。
(2)延遲
延遲指觀察者對網(wǎng)絡(luò)發(fā)出請求到接收到數(shù)據(jù)所歷經(jīng)的時間。
(3)可擴(kuò)展性
在某些特殊的實(shí)際應(yīng)用中，被監(jiān)測區(qū)域需要大量節(jié)點(diǎn)。這樣就要求路由協(xié)議能夠協(xié)同大量節(jié)點(diǎn)同時工作。
2路由協(xié)議的路由通訊量分析
LEACH通過劃分簇層和數(shù)據(jù)融合技術(shù)減少數(shù)據(jù)通訊量。TEEN采用相似的層次通訊方式，并使用軟門閥值和硬門閥值控制數(shù)據(jù)傳輸?shù)拇螖?shù)。PEGASIS通過有效的鏈?zhǔn)綌?shù)據(jù)聚合和數(shù)據(jù)融合技術(shù)，減少了的數(shù)據(jù)收發(fā)次數(shù)和數(shù)據(jù)通訊量。圖3是兩者之間以及和FLOODING洪泛協(xié)議通訊量比較。
SPIN采用基于數(shù)據(jù)描述的協(xié)商機(jī)制進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)，從而避免了產(chǎn)生要轉(zhuǎn)發(fā)數(shù)據(jù)的大量副本。
DIRECTED DIFFUSION采用請求驅(qū)動的數(shù)據(jù)傳送模式和局部的數(shù)據(jù)聚集、融合，減少網(wǎng)絡(luò)數(shù)據(jù)通訊量。圖4是這兩種協(xié)議間以及和FLOODING之間通訊量大小示意表示。
GPSR將數(shù)據(jù)發(fā)送給符合要求的下一跳鄰居。針對某個特定節(jié)點(diǎn)A，在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不發(fā)生變化的情況下，發(fā)送數(shù)據(jù)的路由比較固定。GEAR考慮到匯聚節(jié)點(diǎn)的地理位置信息，并將其添加到數(shù)據(jù)包的地理信息字段，數(shù)據(jù)傳輸?shù)教囟ǚ较颉?/p>
3路由協(xié)議的路由延遲分析
DIRECTED DIFFUSION在數(shù)據(jù)傳輸階段采用一條“梯度”最大路徑。數(shù)據(jù)傳輸時間短。LEACH采用劃分簇層方式減少路由中間的傳感器數(shù)量，也具備短延遲特性。TEEN協(xié)議延遲也比較小，和LEACH同屬于層次式路由協(xié)議。GPSR只依賴直接相鄰的節(jié)點(diǎn)進(jìn)行路由。因?yàn)槭褂媒咏疃虤W式距離的路由，因此數(shù)據(jù)傳輸延遲短。GEAR采用了域內(nèi)和位置區(qū)域地理位置劃分，這樣減少了路由上的跳數(shù)，數(shù)據(jù)能及時到達(dá)匯聚節(jié)點(diǎn)。
PEGASIS數(shù)據(jù)延遲和簇頭位置有很大的關(guān)系。普通節(jié)點(diǎn)距簇頭的地理位置比較遠(yuǎn)，會明顯增加數(shù)據(jù)傳輸?shù)难舆t。SPIN采用三種消息模型來信息擴(kuò)散整個網(wǎng)絡(luò)。解決了FLOODING中的“信息內(nèi)爆”和“信息重疊”問題，但此消息模型導(dǎo)致延遲增加。
圖5給出了層次性協(xié)議在相應(yīng)延遲示意比較。表2作了路由延遲分析的總結(jié)。
4路由協(xié)議的可擴(kuò)展性分析
某些協(xié)議，因節(jié)點(diǎn)大量增加導(dǎo)致網(wǎng)絡(luò)數(shù)據(jù)通訊量過大、路由數(shù)據(jù)的延遲過長等等而不適用于網(wǎng)絡(luò)。
TEEN不斷加入節(jié)點(diǎn)形成新簇層。子簇頭數(shù)據(jù)會向父簇頭傳送，不必像LEACH協(xié)議一樣要求普通節(jié)點(diǎn)必須具備和匯聚節(jié)點(diǎn)直接通訊的能力。
DIRECTED DIFFUSION也具備良好可擴(kuò)展?！疤荻葓觥钡慕⒋_保了數(shù)據(jù)傳輸?shù)募皶r性。備用路徑保證了路由的暢通性、可靠性。
GPSR有可達(dá)路由只要求保持網(wǎng)絡(luò)連通性。GEAR具備好的可擴(kuò)展性，但需要GPS定位信息的支持。即使增加節(jié)點(diǎn)，在地理位置和“兩個階段”的支持下，不會影響協(xié)議。
PEGASIS可擴(kuò)展性差。當(dāng)大量節(jié)點(diǎn)涌入到網(wǎng)絡(luò)中，要構(gòu)造的數(shù)據(jù)鏈長度會急劇增加。將數(shù)據(jù)傳送到簇頭，不僅耗費(fèi)大量能量還增加延時時間。
SPIN可擴(kuò)展性差。當(dāng)產(chǎn)生或收到數(shù)據(jù)的節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)都不需要該數(shù)據(jù)時，將導(dǎo)致數(shù)據(jù)不能繼續(xù)轉(zhuǎn)發(fā)?？赡軐?dǎo)致相當(dāng)部分網(wǎng)絡(luò)不能接收到該數(shù)據(jù)。此外，匯聚節(jié)點(diǎn)對任何類型的數(shù)據(jù)都需要時，周圍的節(jié)點(diǎn)會能量耗盡。表3給出了協(xié)議總結(jié)。
【關(guān)鍵詞】ZigBee網(wǎng)絡(luò) 路由協(xié)議 性能
隨著信息技術(shù)和移動通信技術(shù)的快速發(fā)展，讓無線通信技術(shù)在各行各業(yè)得到了廣泛的應(yīng)用。組網(wǎng)靈活、使用方便是無線傳感器網(wǎng)絡(luò)在實(shí)際應(yīng)用中表現(xiàn)出來的主要特點(diǎn)。ZigBee協(xié)議的出現(xiàn)，可以讓傳統(tǒng)無線協(xié)議對無線傳感器的適應(yīng)問題得到有效解決。
1 ZigBee協(xié)議的概述
ZigBee技術(shù)不僅功耗、成本和速率均比較低，而且便于操作使用。而IEEE 802.15.4標(biāo)準(zhǔn)具有數(shù)據(jù)傳輸率低、成本少、功耗低等特性，其最終目標(biāo)就是為家庭或個人范圍內(nèi)各種設(shè)備之間的低速互連提供一個統(tǒng)一的標(biāo)準(zhǔn)。為了保證所制定出的應(yīng)用層與網(wǎng)絡(luò)層的規(guī)范能夠匹配IEEE802.15.4標(biāo)準(zhǔn)，ZigBee規(guī)范成為ZigBee聯(lián)盟中不可缺少的因素。在與之有關(guān)的LR-WPAN網(wǎng)絡(luò)中，IEEE802.15.4標(biāo)準(zhǔn)編制了以下兩種要素：
（1）系統(tǒng)的媒體接入控制子層；
（2）系統(tǒng)的物理層協(xié)議規(guī)范。
ZigBee聯(lián)盟在這一前提下，所構(gòu)建的應(yīng)用層與網(wǎng)絡(luò)層協(xié)議相關(guān)的規(guī)范構(gòu)成了ZigBee協(xié)議。簡言之，ZigBee協(xié)議是為適應(yīng)IEEE802.15.4標(biāo)準(zhǔn)而構(gòu)建的網(wǎng)絡(luò)層與應(yīng)用層協(xié)議規(guī)范。其中，協(xié)議規(guī)范可以由以下幾方面因素組成：
（1）應(yīng)用支持子層；
（2）應(yīng)用架構(gòu)；
（3）ZigBee設(shè)備對象和廠商所定義的應(yīng)用對象。
分層結(jié)構(gòu)是這一協(xié)議所采用的主要結(jié)構(gòu)。數(shù)據(jù)實(shí)體和管理實(shí)體這兩種服務(wù)實(shí)體在這種結(jié)構(gòu)的每一層都有所涉及。數(shù)據(jù)傳輸服務(wù)是數(shù)據(jù)實(shí)體所承擔(dān)的主要形式。管理實(shí)體提供的服務(wù)中并沒有涉及到數(shù)據(jù)傳輸服務(wù)。服務(wù)接入點(diǎn)是為上層提供接口的重要工具。服務(wù)原語命令是服務(wù)接入點(diǎn)實(shí)現(xiàn)自身功能的保障性因素。圖1中的內(nèi)容就是協(xié)議層之間的服務(wù)接口。
2 ZigBee網(wǎng)絡(luò)拓?fù)?/p>
ZigBee網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)主要由以下幾種結(jié)構(gòu)組成：
（1）星型結(jié)構(gòu)；
（2）樹形結(jié)構(gòu)，
（3）網(wǎng)狀結(jié)構(gòu)。
如圖2所示。
從圖中所示的內(nèi)容來看，中心協(xié)調(diào)器和終端節(jié)點(diǎn)是星型網(wǎng)絡(luò)中的主要器件。這種中心協(xié)調(diào)器采用的是FFD節(jié)點(diǎn)，可以在整個網(wǎng)絡(luò)的維護(hù)和建立過程中發(fā)揮出自身的功能。RFD和FFD是終端節(jié)點(diǎn)主要組成部分，一般的情況下，在中心協(xié)調(diào)器覆蓋范圍以內(nèi)的區(qū)域是這兩大節(jié)點(diǎn)的主要分布區(qū)域，@種便利性可以讓這些節(jié)點(diǎn)與中心協(xié)調(diào)器進(jìn)行有效通信的能力得到有效提升。兩個不同設(shè)備之間進(jìn)行通信的過程，也是兩設(shè)備將各自所要傳送的數(shù)據(jù)包向中心協(xié)調(diào)器進(jìn)行傳送的過程。可以說，中心協(xié)調(diào)器發(fā)揮的是一種中轉(zhuǎn)作用。對中心協(xié)調(diào)器的中轉(zhuǎn)功能進(jìn)行發(fā)揮的網(wǎng)絡(luò)系統(tǒng)又被稱為主從網(wǎng)絡(luò)。同步與控制的簡單性特點(diǎn)是星型網(wǎng)的主要特點(diǎn)，這種網(wǎng)絡(luò)體系目前僅能在一些擁有較少節(jié)點(diǎn)數(shù)量的場合中得到應(yīng)用。網(wǎng)狀網(wǎng)絡(luò)是一種由多個FFD組合而成的骨干網(wǎng)絡(luò)，各節(jié)點(diǎn)之間的通信完全對等，在整個通信范圍內(nèi)，各節(jié)點(diǎn)都可以與其它節(jié)點(diǎn)進(jìn)行通信。如果其中一條路徑發(fā)生故障，那么還可以選擇其他一條或若干條路徑。然而，正是因?yàn)閮蓚€節(jié)點(diǎn)之間的路徑較多，所以顯得冗余非常高。一般情況下，路由功能的實(shí)現(xiàn)，是網(wǎng)狀網(wǎng)絡(luò)構(gòu)建過程中所遵循的一個重要原則，此種有助于網(wǎng)絡(luò)層找到最佳的信息傳遞路徑，事實(shí)上屬于一種多信道通信。樹狀拓?fù)浣Y(jié)構(gòu)主要由以下三個部分組成：
（1）中心協(xié)調(diào)器；
（2）路由節(jié)點(diǎn)；
（3）終端節(jié)點(diǎn)。
在實(shí)際應(yīng)用過程中，連接路由節(jié)點(diǎn)和終端節(jié)點(diǎn)的功能是該結(jié)構(gòu)的主要功能。在路由節(jié)點(diǎn)成為中心協(xié)調(diào)器子節(jié)點(diǎn)的情況下，這一結(jié)構(gòu)會借助一系列的終端節(jié)點(diǎn)與路由節(jié)點(diǎn)相連。終端節(jié)點(diǎn)不能涵蓋自身的子節(jié)點(diǎn)，但路由節(jié)點(diǎn)與中心協(xié)調(diào)器可以涵蓋自身的子節(jié)點(diǎn)。在樹狀拓?fù)浣Y(jié)構(gòu)中，各個節(jié)點(diǎn)只具備一種功能，就是實(shí)現(xiàn)子節(jié)點(diǎn)與父節(jié)點(diǎn)之間的通訊。在這樣的情況下，如果要將一個節(jié)點(diǎn)中的數(shù)據(jù)傳輸?shù)搅硪粋€節(jié)點(diǎn)，這種樹狀結(jié)構(gòu)會讓信息順著樹的路徑進(jìn)行輸送。網(wǎng)絡(luò)覆蓋范圍大是這一網(wǎng)絡(luò)結(jié)構(gòu)的主要特點(diǎn)。由于信息路由通道在該系統(tǒng)中存在單一性，隨著網(wǎng)絡(luò)覆蓋范圍增加，信息的傳輸時延也會有所增加，并且時間同步也會越來越繁瑣。
3 ZigBee網(wǎng)絡(luò)路由協(xié)議的性能
3.1 路由協(xié)議的基本思想
低成本、低功效和高可靠性是ZigBee網(wǎng)絡(luò)路由協(xié)議的主要設(shè)計(jì)目標(biāo)。樹路由和按需距離矢量路由相結(jié)合的路由算法的構(gòu)建，為上述目標(biāo)的實(shí)現(xiàn)提供了幫助。在對ZigBee網(wǎng)絡(luò)中使用的AODVjr與自組網(wǎng)中所應(yīng)用的AODV協(xié)議進(jìn)行對比分析以后，我們可以發(fā)現(xiàn)，AODVjr可以被看作是AODV的一種簡化版本。在ZigBee網(wǎng)絡(luò)中，節(jié)點(diǎn)之間存在一種類似于父子關(guān)系的從屬關(guān)系。在依托路由算法進(jìn)行路徑選擇的過程中，節(jié)點(diǎn)會在接收到分組信息以后對信息進(jìn)行判斷，如果發(fā)現(xiàn)其中的內(nèi)容與自己無關(guān)，會把該信息傳送給其父節(jié)點(diǎn)或其他子節(jié)點(diǎn)。為了對路由效率進(jìn)行進(jìn)一步的提升，AODVjr也會為一些具備路由功能的節(jié)點(diǎn)搜尋路由，也就是說，在傳輸信息的過程中，在不遵從父子從屬關(guān)系的情況下，通過直接傳遞的方式將信息傳送到其通信范圍內(nèi)的其他具備同樣功能的節(jié)點(diǎn)的措施，是一些具備路由功能的節(jié)點(diǎn)進(jìn)行信息傳輸?shù)闹饕胧?，而針對那些不具備路由功能的?jié)點(diǎn)，則只能借助樹路由來對控制分組與數(shù)據(jù)分組進(jìn)行傳輸。
3.2 ZigBee的路由過程
在zigBee網(wǎng)絡(luò)路由協(xié)議中，節(jié)點(diǎn)既具備路由表能力，又具有路由發(fā)現(xiàn)表能力，表1所示的內(nèi)容為路由發(fā)現(xiàn)表的格式
從階段網(wǎng)絡(luò)層的數(shù)據(jù)幀獲取情況來看，在網(wǎng)絡(luò)層從更高層接受數(shù)據(jù)幀的情況下，廣播發(fā)送是節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳送的主要方式。在接收節(jié)點(diǎn)為路由器或協(xié)調(diào)器的情況下，如果數(shù)據(jù)幀的目的節(jié)點(diǎn)是該節(jié)點(diǎn)的子節(jié)點(diǎn)，這一數(shù)據(jù)幀會被直接傳送到目的地址之中。如果網(wǎng)絡(luò)層接收的是來自低層的數(shù)據(jù)幀，數(shù)據(jù)幀的目的節(jié)點(diǎn)成為了系統(tǒng)對數(shù)據(jù)幀的發(fā)送方式進(jìn)行確定的主要方式。在對一些具備路由功能的節(jié)點(diǎn)進(jìn)行確定的過程中，系統(tǒng)會對目的地址在路由表中的地址加以核查，在節(jié)點(diǎn)目的地址的路由條目不確定的情況下，首先針對數(shù)據(jù)幀頭系統(tǒng)需要對幀控制域中的路由發(fā)現(xiàn)標(biāo)志進(jìn)行核查，如果路由發(fā)現(xiàn)標(biāo)志值為0，或者此節(jié)點(diǎn)缺少路由功能，則可采取樹路由的方式傳輸數(shù)據(jù)幀；倘若該發(fā)現(xiàn)路由標(biāo)志值為1，則該節(jié)點(diǎn)可根據(jù)路由發(fā)現(xiàn)的發(fā)起方式及條件來發(fā)起路由發(fā)現(xiàn)。針對目的地址的路由條目明確的節(jié)點(diǎn)，必須借助已有路由表?xiàng)l目進(jìn)行路由傳輸。
如果網(wǎng)絡(luò)層接收到來源于低層的數(shù)據(jù)幀，則是否需要轉(zhuǎn)發(fā)該數(shù)據(jù)幀主要取決于該數(shù)據(jù)幀的目的節(jié)點(diǎn)是否是本地節(jié)點(diǎn)。在終端設(shè)備成為目的節(jié)點(diǎn)以后，設(shè)備在應(yīng)用過程中出現(xiàn)的休眠問題會給信息的傳輸效率帶來不利的影響。間接傳遞方式的應(yīng)用，就成為了對休眠效應(yīng)的不利影響進(jìn)行規(guī)避的有效方式。數(shù)據(jù)幀頭中的Discover Route字段決定著如何選取ZigBee網(wǎng)絡(luò)層的具體路由方法。
3.3 路由選擇
在節(jié)點(diǎn)的職能定義和工作狀態(tài)存在一定差異性的情況下，路由策略選擇就成為了zigBee網(wǎng)絡(luò)路由協(xié)議性能的一種表現(xiàn)。路由選擇策略主要由以下幾種策略組成。
（1）抑制路由發(fā)現(xiàn)，這一性能是建立在已經(jīng)存在的路由表基礎(chǔ)之上的；
（2）使能路由的發(fā)現(xiàn)，即路由表中存在該路由地址，則按路由表執(zhí)行，否則路由器進(jìn)行初始化路由發(fā)現(xiàn)處理。如果路由表中的節(jié)點(diǎn)不具備初始路由的發(fā)現(xiàn)能力，系統(tǒng)會對樹形路由進(jìn)行運(yùn)用；
（3）強(qiáng)制路由發(fā)現(xiàn)功能，在這一功能的作用下，不論相應(yīng)的路由表是否存在，節(jié)點(diǎn)都會在對AODVjr路由算法進(jìn)行強(qiáng)制應(yīng)用的情況下進(jìn)行初始化路由發(fā)現(xiàn)?？梢哉f，數(shù)據(jù)驅(qū)動思想是與數(shù)據(jù)的傳輸種類和傳輸需要之間存在著一定的聯(lián)系；
（4）樹路由發(fā)現(xiàn)功能，即只應(yīng)用樹狀路由方式發(fā)起路由發(fā)現(xiàn)，且不遵從現(xiàn)有的路由表。所謂的數(shù)據(jù)驅(qū)動思想就是指針對不同類型及需求的數(shù)據(jù)傳遞，可以采取多種路由方式。如果需要傳遞大量的數(shù)據(jù)，那么可以對使能路由發(fā)現(xiàn)功能加以選取，發(fā)現(xiàn)并構(gòu)建最佳路徑。如果需要傳遞控制數(shù)據(jù)或突發(fā)型數(shù)據(jù)，則可以對樹路由發(fā)現(xiàn)功能與抑制路由發(fā)現(xiàn)功能加以選取，這兩種路由發(fā)現(xiàn)功能能夠?qū)崿F(xiàn)快速響應(yīng)，而且不需要構(gòu)建路由表。如果需要更新路由表內(nèi)的信息，那么可以對強(qiáng)制路由發(fā)現(xiàn)功能加以選取，以此來對路由表進(jìn)行更新，對路由表加以重新構(gòu)建。
4 結(jié)論
ZigBee結(jié)束對進(jìn)場通信市場所表現(xiàn)出的低成本、低速率和低功耗的問題進(jìn)行了有效解決。這一技術(shù)的應(yīng)用，對低端無線傳感器和控制網(wǎng)絡(luò)設(shè)計(jì)的優(yōu)化有著一定的促進(jìn)作用。ZigBee通過結(jié)合ZigBee規(guī)范與IEEE802.15.4標(biāo)準(zhǔn)，可以有效的實(shí)現(xiàn)數(shù)以萬計(jì)的微波傳感器之間進(jìn)行協(xié)同通信。在當(dāng)下ZigBee快速發(fā)展、不斷優(yōu)化的新時代下，ZigBee技術(shù)勢必會為無線接入技術(shù)領(lǐng)域注入全新的活力，必將使人們的生活模式及工作模式發(fā)生翻天覆地的改變，促進(jìn)社會以及經(jīng)濟(jì)建設(shè)更快、更好地發(fā)展。
參考文獻(xiàn)
[1]張習(xí)勝.ZigBee無線網(wǎng)絡(luò)協(xié)議的路由算法分析與實(shí)現(xiàn)[J].電子元器件應(yīng)用，2010（07）：53-56.
[2]關(guān)學(xué)忠，張新城，孟伸伸.基于ZigBee技術(shù)的無線傳感器網(wǎng)絡(luò)路由算法的性能分析[J].自動化技術(shù)與應(yīng)用，2017（03）：36-39.
作者簡介
李玉林（1981-），男，湖南省永興縣人。碩士學(xué)位。現(xiàn)為湖南機(jī)電職業(yè)技術(shù)學(xué)院講師。主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)管理。
Abstract: Ad hoc network is a MANET, mobile nodes must have the routing function, so the routing protocol selection is critical. This paper introduces the DSDV, DSR and AODV routing protocols. We obtain the throughput, packet loss and delay performance analysis chart by NS simulation. It gives the advantages and disadvantages of these types of routing protocols and the future direction of development of routing protocols.
關(guān)鍵詞： Ad hoc網(wǎng)絡(luò)；NS模擬；DSDV；DSR；AODV
Key words: Ad hoc network；NS simulation；DSDV；DSR；AODV
中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：1006-4311（2011）17-0146-02
0引言
移動Ad hoc網(wǎng)絡(luò)是一種自組網(wǎng)，不需要固定的基礎(chǔ)設(shè)施，能夠快速地自動組網(wǎng)。與有中心網(wǎng)絡(luò)相比，Ad hoc網(wǎng)絡(luò)靈活、健壯、投資少，特別適合于作戰(zhàn)指揮、搶險(xiǎn)救災(zāi)以及應(yīng)付突發(fā)事件和執(zhí)行臨時任務(wù)的場合。在Ad hoc網(wǎng)絡(luò)中，因?yàn)樽越M網(wǎng)中節(jié)點(diǎn)的傳輸范圍有限，源端向目的端發(fā)送數(shù)據(jù)時，通常需要其它節(jié)點(diǎn)的輔助，所以路由協(xié)議是自組網(wǎng)中不可缺少的一部分。路由協(xié)議的功能是根據(jù)路由策略和路由表進(jìn)行數(shù)據(jù)分組轉(zhuǎn)發(fā)和路由維護(hù)。Ad hoc網(wǎng)絡(luò)在通信中，節(jié)點(diǎn)是移動的，而且傳輸能力有限，大多采用多跳轉(zhuǎn)播通信，而多跳路由帶寬受限，設(shè)備功率低，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)動態(tài)變化，易受攻擊等挑戰(zhàn)。
1Ad hoc路由協(xié)議及典型的路由算法
目前，Ad hoc網(wǎng)絡(luò)的路由協(xié)議大致可以分為主動路由協(xié)議、按需路由協(xié)議和混合路由協(xié)議。主動路由協(xié)議又稱為表驅(qū)動路由協(xié)議，在這種路由協(xié)議中，即使沒有傳輸需求，兩節(jié)點(diǎn)之間的路由也預(yù)先建立。這種方法不適合大規(guī)模網(wǎng)絡(luò)，許多不用的路由仍需維持，而且還有周期性的路由信息更新。而按需路由協(xié)議，是一種當(dāng)需要發(fā)送數(shù)據(jù)時才建立路由。不需要時，釋放路由。然而，當(dāng)一個鏈路失效或節(jié)點(diǎn)斷開，要重建路由而引起延時和開銷更嚴(yán)重。下面介紹幾種典型的路由算法。
1.1 主動路由協(xié)議――DSDV目的節(jié)點(diǎn)序列距離矢量路由協(xié)議（DSDV，Destination-Sequenced Distance-Vector Routing）是基于Bellman-Ford算法，在DSDV中，每個移動節(jié)點(diǎn)都需要維護(hù)一個路由表。路由表包括目的節(jié)點(diǎn)、跳數(shù)、下一跳節(jié)點(diǎn)和目的地序號，其中目的地序號由目的節(jié)點(diǎn)分配，主要用于判別路由是否過時，并可防止路由環(huán)路的產(chǎn)生。每個節(jié)點(diǎn)周期性必須與鄰節(jié)點(diǎn)交換路由信息，當(dāng)然也可以根據(jù)路由表的改變來觸發(fā)路由更新。對路由表進(jìn)行更新主要有以下兩種方式：①全部更新：拓?fù)涓孪⒅袑⒑w整個路由表。此種方式大多運(yùn)用在有相對快的網(wǎng)絡(luò)變化的狀況下；②部分更新：在更新消息中只是涵蓋了變化的路由部分。這種方式大多應(yīng)用在有相對較慢的網(wǎng)絡(luò)變化的狀況。在DSDV中只要從源到目的的路由存在，這種路由協(xié)議的所需時延較小，缺點(diǎn)是路由協(xié)議的開銷較大，因?yàn)閯討B(tài)的拓?fù)浣Y(jié)構(gòu)變化，使得路由信息更新復(fù)雜，不適合大規(guī)模的網(wǎng)絡(luò)。
1.2 按需路由協(xié)議――DSR動態(tài)源路由協(xié)議（DSR，Dynamic Source Routing Protocol）是一種基于源路由的按需路由協(xié)議，它使用源路由算法而不是逐跳路由的方法。DSR主要包括兩個過程：路由發(fā)現(xiàn)和路由維護(hù)。當(dāng)節(jié)點(diǎn)S向節(jié)點(diǎn)D發(fā)送數(shù)據(jù)時，它首先檢查緩存是否存在未過期的到目的節(jié)點(diǎn)的路由，如果存在，則直接使用可用的路由，否則啟動路由發(fā)現(xiàn)過程。路由發(fā)現(xiàn)過程是：源端節(jié)點(diǎn)廣播路由請求給其鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)收到路由請求分組后，輪流把自己的地址添加道路由請求分組，并轉(zhuǎn)發(fā)補(bǔ)充了的路由請求分組，這個過程一直持續(xù)到有一個路由請求分組到達(dá)目的端節(jié)點(diǎn)。若發(fā)現(xiàn)自己的地址在記錄中，就停止廣播，每個節(jié)點(diǎn)都有一個路由緩存，存貯最近轉(zhuǎn)發(fā)來的路由請求，同時查詢接收的是否為統(tǒng)一個請求，這樣可以保證每個節(jié)點(diǎn)之轉(zhuǎn)發(fā)一次。當(dāng)路由請求到達(dá)目的節(jié)點(diǎn)時，節(jié)點(diǎn)要返回一個路由應(yīng)答分組，通知節(jié)點(diǎn)已收到該路由請求。目的節(jié)點(diǎn)通過反向路由來發(fā)送路有應(yīng)答消息。那么源端與目的端有多條路由。DSR把這些路由緩存在路由緩存器中備用。
這樣做DSR不需要周期性的發(fā)送路由發(fā)現(xiàn)報(bào)文，但發(fā)送每個報(bào)文都要攜帶完整的路由消息。降低帶寬的利用率。DSR的優(yōu)點(diǎn)：①節(jié)點(diǎn)僅需要維護(hù)與之通信的節(jié)點(diǎn)的路由，減少了協(xié)議開銷；②使用路由緩存技術(shù)減少了路由發(fā)現(xiàn)的耗費(fèi)；③一次路由發(fā)現(xiàn)過程可能會產(chǎn)生多條到目的點(diǎn)的路由。DSR的缺點(diǎn)：①每個數(shù)據(jù)報(bào)文的頭部都需要攜帶路由信息，數(shù)據(jù)包的額外開銷較大；②路由請求消息采用洪泛方式，相鄰節(jié)點(diǎn)路由請求消息可能發(fā)生傳播沖突并可能會產(chǎn)生重復(fù)廣播；③由于緩存，過期路由會影響路由選擇的準(zhǔn)確性。
1.3 按需路由協(xié)議――AODV Ad hoc按需距離矢量路由協(xié)議（AODV, Ad hoc on Demand Distance Vector）是DSDV算法的改進(jìn)，但它與DSDV的區(qū)別在于它是按需路由協(xié)議。為了找到通往目的節(jié)點(diǎn)的路由，源端將廣播一個路由請求分組，鄰居節(jié)點(diǎn)依次向周圍節(jié)點(diǎn)廣播此分組直到該分組被送到一個知道目的節(jié)點(diǎn)路由信息中間節(jié)點(diǎn)或目的節(jié)點(diǎn)本身。一個節(jié)點(diǎn)將丟棄重復(fù)收到的請求分組，路由請求分組中的序列號用來防止路由環(huán)路，并能判斷中間節(jié)點(diǎn)是否響應(yīng)了相應(yīng)的路由請求。當(dāng)節(jié)點(diǎn)轉(zhuǎn)發(fā)路由請求分組時，它會將其上一個節(jié)點(diǎn)的標(biāo)志ID記入路由表，從而能夠構(gòu)建一條從目的節(jié)點(diǎn)到源節(jié)點(diǎn)的反向路由。當(dāng)源端移動時，它會重新發(fā)起路由發(fā)現(xiàn)算法；如果中間節(jié)點(diǎn)移動，那么與其相鄰的節(jié)點(diǎn)會發(fā)現(xiàn)鏈路失效并向其上一個節(jié)點(diǎn)發(fā)送鏈路失效消息并一直傳到源節(jié)點(diǎn)，而后源節(jié)點(diǎn)根據(jù)情況重新發(fā)起路由發(fā)現(xiàn)過程。
2Ad hoc網(wǎng)絡(luò)中的路由協(xié)議的NS模擬
本模擬在windows XP環(huán)境下，采用Cygwin和ns-allinone-2.28搭建模擬平臺。在此環(huán)境下，對Ad hoc網(wǎng)絡(luò)中的路由協(xié)議DSDV、DSR和AODV進(jìn)行模擬分析，并對其進(jìn)行性能比較，并以圖形形式顯示。
2.1 搭建實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)淠M工具采用NS2網(wǎng)絡(luò)模擬器，無線模擬開始時，需要定義每個網(wǎng)絡(luò)功能組件的類型，包括天線的類型、電磁波的傳輸模式和移動節(jié)點(diǎn)使用的Ad hoc路由選擇協(xié)議等。網(wǎng)絡(luò)初始拓?fù)浣Y(jié)構(gòu)見圖1，該模型由6個無線移動節(jié)點(diǎn)構(gòu)成，3個源節(jié)點(diǎn)（節(jié)點(diǎn)0，1和2）和3個目的節(jié)點(diǎn)（節(jié)點(diǎn)3，4和5）。節(jié)點(diǎn)0開始向節(jié)點(diǎn)3發(fā)送CBR數(shù)據(jù)包，使用的是DSDV路由協(xié)議；節(jié)點(diǎn)1開始向節(jié)點(diǎn)4發(fā)送CBR數(shù)據(jù)包，使用的是DSR路由協(xié)議；節(jié)點(diǎn)2開始向節(jié)點(diǎn)5發(fā)送CBR數(shù)據(jù)包，使用的是AODV路由協(xié)議；傳輸?shù)姆纸M大小均是512比特，傳輸速率是600 Kbps，開始傳輸時間為1.4s，傳輸距離是195米，模擬的時間是80s。
2.2 性能分析在相同的網(wǎng)絡(luò)環(huán)境下，分別用3種Ad hoc路由協(xié)議進(jìn)行模擬，而后對模擬產(chǎn)生的TR數(shù)據(jù)進(jìn)行分析，用繪圖工具Xgraph繪制，由于本模擬是從1.4s開始模擬，但是繪制的吞吐量、丟包和延時圖卻是從0s開始。吞吐量實(shí)時變化圖如圖2，丟包實(shí)時變化圖如圖3，端到端的延時的實(shí)時變化圖如圖4所示，黑色是DSR，深灰色是DSDV，淺灰色是AODV。下面進(jìn)行具體的分析比較3種路由協(xié)議下CBR應(yīng)用的性能。
2.2.1 吞吐量吞吐量能反映網(wǎng)絡(luò)占用帶寬的性能。從圖2可知，從1.4s到20s時，AODV的吞吐量最大，DSDV和DSR差不多；20s后，3種路由協(xié)議的吞吐量都比剛開始模擬要小一些，呈現(xiàn)不斷降低的趨勢。吞吐量是AODV最好，次之是DSR，DSDV最差。
2.2.2 丟包率丟包率反映的是丟包數(shù)目與總發(fā)包數(shù)目的比值。從圖3可知，從1.4s到20s時，3種路由協(xié)議都沒有丟包，但20s后，丟包率都增加，呈現(xiàn)不斷提高的趨勢。其中，丟包最大的是DSDV，然后是DSR，最小的是AODV。
2.2.3 端到端的延時端到端的延時是反映包發(fā)送過程中，目的端與源端的時間差。從圖4可知，從1.4s到20s時，3種路由協(xié)議端到端的延時一致，呈現(xiàn)不斷提高的趨勢。但20s后，端到端的延時都增加，其中，延時最大的是DSR，然后是AODV，最小的是DSDV。
綜上所述，都是因?yàn)镈SDV是主動路由協(xié)議，而DSR、AODV是需路由協(xié)議，DSDV為目的節(jié)點(diǎn)只維護(hù)一個路由，當(dāng)此路由失效時將沒有可以替換的路由。如果網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化的太快，路由信息更新復(fù)雜，網(wǎng)絡(luò)開銷大，端到端的延時小一些。而按需路由是不用周期的廣播信息，節(jié)省網(wǎng)絡(luò)開銷，但每次要進(jìn)行路由發(fā)現(xiàn)，端到端的時延大。
3結(jié)論
本文詳細(xì)分析了當(dāng)前Ad hoc網(wǎng)絡(luò)采用的3種路由協(xié)議，并且通過NS網(wǎng)絡(luò)模擬器對其中的3種路由算法進(jìn)行了模擬分析和性能比較。結(jié)果表明不同的路由協(xié)議都有各自的應(yīng)用場合和優(yōu)缺點(diǎn)，目前最為流行的就是將主動和按需路由協(xié)議優(yōu)點(diǎn)的混合式路由協(xié)議是一種較好的折衷方案。應(yīng)用在局部范圍內(nèi)使用主動路由協(xié)議，維護(hù)準(zhǔn)確的路由信息，并可縮小路由控制消息傳播的范圍，當(dāng)目標(biāo)節(jié)點(diǎn)較遠(yuǎn)時，通過查找發(fā)現(xiàn)路由，這樣既可以減少路由協(xié)議的開銷，時延特性也得到了改善。這種路由算法吸取了2種路由算法的優(yōu)點(diǎn)，具有較高的效率和較強(qiáng)的適應(yīng)性。由于Ad hoc自身復(fù)雜多變的動態(tài)特性，路由協(xié)議的設(shè)計(jì)目前仍是一個人們關(guān)注的熱點(diǎn)問題。
參考文獻(xiàn)：
[1]李平均,谷寧靜.一種基于AODV協(xié)議的改進(jìn)協(xié)議Q-AODV[J].微電子學(xué)與計(jì)算機(jī)，2006,23(5）:89-92.
[2]王金龍,王呈貴,吳啟暉等.Ad hoc移動無線網(wǎng)絡(luò)[M].北京:國防工業(yè)出版社，2004.
[3]葛文英,偉.Ad hoc網(wǎng)絡(luò)的按需路由研究[J].軟件技術(shù).2006,(8):41-42.
[4]于斌,孫斌,溫暖等.NS-2與網(wǎng)絡(luò)模擬[M].北京：人民郵電出版社，2007.
關(guān)鍵詞：無線傳感網(wǎng)絡(luò)；RPL；IP；能量路由
中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號：2095-1302（2014）01-0057-03
0 引 言
低功耗有損網(wǎng)絡(luò)路由協(xié)議 （RPL）是IETF的ROLL（Routing Over Low power and Lossy networks ）工作組，專門針對低功耗有損網(wǎng)絡(luò)LLN（Low power and Lossy network）新提出來的路由協(xié)議[1]。低功耗有損網(wǎng)絡(luò)是由功率、存儲空間、處理能力等資源受限的嵌入式設(shè)備所組成的網(wǎng)絡(luò)。它們可以通過多種鏈路連接，比如IEEE 802.15.4、藍(lán)牙、低功率Wi-Fi，甚至低功耗電力線通信（PLC）等等。ROLL將LLN網(wǎng)絡(luò)的應(yīng)用主要劃分為四個領(lǐng)域[2]：城市網(wǎng)絡(luò)（包括智能電網(wǎng)應(yīng)用）、建筑自動化、工業(yè)自動化以及家庭自動化，并且分別制定了針對四個應(yīng)用領(lǐng)域的路由需求[3-6]。由于LLN的獨(dú)特性，傳統(tǒng)的IP路由協(xié)議，比如OSPF、IS-IS、AODV、OLSR，無法滿足其獨(dú)特的路由需求，因此ROLL工作組制定了RPL協(xié)議，其協(xié)議標(biāo)準(zhǔn)RFC6550[1]于2012年3月。
本論文首先介紹了RPL的應(yīng)用場景及基本原理，并在路徑選擇策略中加入了對節(jié)點(diǎn)剩余能量的考慮；最后通過仿真驗(yàn)證了改進(jìn)后的路由協(xié)議的性能。
1 RPL協(xié)議工作原理
RPL是一個矢量路由協(xié)議，通過構(gòu)建有向非循環(huán)圖（DAG）來形成拓?fù)浣Y(jié)構(gòu)，加入DAG中的節(jié)點(diǎn)自動形成一條指向根節(jié)點(diǎn)的路徑。RPL主要為數(shù)據(jù)匯聚型的場景設(shè)計(jì)，即數(shù)據(jù)流量由葉節(jié)點(diǎn)指向根節(jié)點(diǎn)。當(dāng)然RPL也擴(kuò)展支持多點(diǎn)對點(diǎn)（MP2P）和點(diǎn)對點(diǎn)（P2P）的應(yīng)用場景。
圖1所示為典型的DAG結(jié)構(gòu)。其中的每一個節(jié)點(diǎn)至少有一條指向根節(jié)點(diǎn)的路徑。
1.1 DODAG的形成
DODAG（Destination Oriented Directed Acyclic Graph）是面向目的地的有向非循環(huán)圖的簡稱，可以視為物理網(wǎng)絡(luò)上的邏輯路由拓?fù)洹?/p>
RPL中定義了由多種ICMPv6消息來控制拓?fù)涞男纬?。DIO消息用于通告有關(guān)DODAG的參數(shù)，例如DODAGID、目標(biāo)函數(shù)（OF）、DODAG版本號等[1]。其中OF規(guī)定了拓?fù)浣⒓白顑?yōu)父節(jié)點(diǎn)的選擇方式，規(guī)定了節(jié)點(diǎn)級別的計(jì)算方法，是路徑選擇的首要參考標(biāo)準(zhǔn)。級別決定了節(jié)點(diǎn)在DODAG中的相對位置，主要用于避免回路。DAO消息是用來建立從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的“向下”的路徑。根據(jù)節(jié)點(diǎn)的存儲能力，RPL協(xié)議中將節(jié)點(diǎn)類型定義為可存儲型和非存儲型，兩者的區(qū)別在于是否存儲有路由表信息。在圖1中，當(dāng)D節(jié)點(diǎn)要和E節(jié)點(diǎn)通信時，如果B節(jié)點(diǎn)和C節(jié)點(diǎn)是非存儲型，那么必須先追溯到根節(jié)點(diǎn)A，查找路由，即路徑為D—C—B—A—B—C—E。若C為可存儲型節(jié)點(diǎn)，則只需追溯到共同的祖先節(jié)點(diǎn)即可找到路由，即路徑為D—C—E。DIS消息用于向鄰居節(jié)點(diǎn)請求DODAG信息。當(dāng)一個孤立的節(jié)點(diǎn)沒有收到任何DIO消息的時候，可通過DIS向周圍節(jié)點(diǎn)請求DODAG信息。收到DIS消息的節(jié)點(diǎn)會反饋DIO消息給DIS源節(jié)點(diǎn)。
如圖1所示，首先A節(jié)點(diǎn)通過DIO消息廣播自己創(chuàng)建的DODAG信息，收到DIO消息的節(jié)點(diǎn)根據(jù)OF來決定是否應(yīng)該加入該DODAG；加入之后然后再向自己周圍的節(jié)點(diǎn)繼續(xù)廣播DIO消息；這樣一層一層地建立拓?fù)浣Y(jié)構(gòu)。當(dāng)節(jié)點(diǎn)加入DODAG之后，就自動創(chuàng)建一條“向上”匯聚到根節(jié)點(diǎn)的路徑?！跋蛳隆钡穆窂絼t由DAO消息完成。
1.2 定時器管理
RPL中使用細(xì)流算法[7]來控制DIO消息的發(fā)送。細(xì)流算法是一個適應(yīng)性的機(jī)制，用來限制控制協(xié)議的開銷。與傳統(tǒng)IP網(wǎng)絡(luò)不同，LLN網(wǎng)絡(luò)有著非常有限的資源，必須盡可能的減少控制協(xié)議消息所占的比例，但同時又必須要維護(hù)好網(wǎng)絡(luò)結(jié)構(gòu)。當(dāng)網(wǎng)絡(luò)改變時，節(jié)點(diǎn)會以較高的頻率發(fā)送控制包；當(dāng)網(wǎng)絡(luò)趨于穩(wěn)定時，則控制流的速率減少。算法中定義了控制消息發(fā)送間隔參數(shù)I，當(dāng)網(wǎng)絡(luò)很穩(wěn)定時，則I成倍的增加；而網(wǎng)絡(luò)有動蕩時，則發(fā)送間隔迅速降為最小值，高頻率的發(fā)送控制消息以修復(fù)網(wǎng)絡(luò)。
本文借助Contiki系統(tǒng)中的Cooja模擬器，對RPL協(xié)議進(jìn)行了仿真。圖2所示為節(jié)點(diǎn)布局圖，并在圖3中以節(jié)點(diǎn)5為例展示了DIO消息的發(fā)送控制過程。從圖3中可以看到，當(dāng)網(wǎng)絡(luò)剛形成逐步趨于穩(wěn)定的時候，DIO消息發(fā)送間隔成倍增加；圖3中23：00和01：20附近陡峭的轉(zhuǎn)折點(diǎn)表明此時監(jiān)測到節(jié)點(diǎn)5和網(wǎng)絡(luò)存在不一致性，迅速將控制消息發(fā)送間隔調(diào)至最小值以迅速修復(fù)網(wǎng)絡(luò)。
1.3 環(huán)路避免機(jī)制
RPL中規(guī)定，在沿著葉節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上，節(jié)點(diǎn)級別必須是遞減的[1]，即父節(jié)點(diǎn)的級別必須小于子節(jié)點(diǎn)的級別。當(dāng)節(jié)點(diǎn)在網(wǎng)絡(luò)中位置發(fā)生改變時，必須根據(jù)父節(jié)點(diǎn)重新計(jì)算自己的級別。假設(shè)節(jié)點(diǎn)N的最優(yōu)父節(jié)點(diǎn)為P，P的級別為R（P），那么N的級別R（N）計(jì)算公式為：
R（N）=R（P）+ rank_increase
rank_increase為子節(jié)點(diǎn)和父節(jié)點(diǎn)級別的差值，其算法在OF中有定義。
節(jié)點(diǎn)的級別在環(huán)路避免中有著重要的意義。RPL協(xié)議也通過在包頭上設(shè)定標(biāo)志位來附帶路由控制數(shù)據(jù)，以避免數(shù)據(jù)包被循環(huán)轉(zhuǎn)發(fā)。
2 考慮節(jié)點(diǎn)剩余能量的RPL協(xié)議
2.1 RPL協(xié)議原始路由方案
目標(biāo)函數(shù)決定了RPL協(xié)議的路徑選擇方式。目前RPL的官方文件中，只明確定義了零目標(biāo)函數(shù)（OF0）[8]，即以跳數(shù)（HC）為最佳路徑選擇的唯一標(biāo)準(zhǔn)，而其他的目標(biāo)函數(shù)則由開發(fā)者根據(jù)需求靈活定義。比如對鏈路可靠性要求較高的應(yīng)用，可將鏈路質(zhì)量作為路由選擇的首要考慮標(biāo)準(zhǔn)；而對能量受限的環(huán)境則可以定義在路徑中盡量避開電池供電節(jié)點(diǎn)。在文檔RFC6551[9]中，提出了多種可供開發(fā)者參考的路由度量。
在選擇路徑時，若只考慮跳數(shù)因素，必然會導(dǎo)致Sink周邊節(jié)點(diǎn)數(shù)據(jù)壓力過大，從而使關(guān)鍵節(jié)點(diǎn)能量過早消耗而死亡。文獻(xiàn)[10]將網(wǎng)絡(luò)的生命長度定義為第一個節(jié)點(diǎn)死亡的時間。對于能量受限的低功耗有損網(wǎng)絡(luò)，如何平衡能量消耗，延長網(wǎng)絡(luò)整體壽命，是協(xié)議要考慮的重要因素。
2.2 優(yōu)化之后的RPL路由方案
目前已有多種針對無線傳感網(wǎng)絡(luò)能量優(yōu)化的路由協(xié)議，比如分級能量路由協(xié)議LEACH和TEEN，以數(shù)據(jù)為中心的能量有效路由協(xié)議DD和SPIN，還有基于地理位置的路由協(xié)議GPSR和GEAR等[11]。 但這些協(xié)議都很難實(shí)現(xiàn)和RPL協(xié)議的融合。RPL協(xié)議是通過在container metric中，定義路徑選擇時所考慮的參數(shù)，然后再以一定的方式將所需要考慮的參數(shù)相結(jié)合，從而確定一個合理的路徑選擇方案。
本篇論文中采取的是跳數(shù)（HC）和節(jié)點(diǎn)能量（EN）相結(jié)合的方式。結(jié)合方式有兩種[12]，一種是Lex，一種是Add。Lex是指優(yōu)先考慮跳數(shù)，只有在跳數(shù)相同的情況下，才考慮節(jié)點(diǎn)能量；而Add則是采取兩種參數(shù)綜合考慮的方式，按照一定的比例相結(jié)合，即：
其中：
本文對這兩種不同的結(jié)合方式做了仿真對比。
2.3 RPL協(xié)議改進(jìn)前后的仿真對比
仿真工具采用的是美國UIUC大學(xué)開發(fā)的針對無線傳感網(wǎng)絡(luò)研究的J-Sim平臺，該平臺基于Java語言，和NS2相比具有內(nèi)存消耗小、仿真速度快、有更好的可擴(kuò)展性等優(yōu)點(diǎn)。本文仿真了傳感網(wǎng)絡(luò)數(shù)據(jù)收集的場景。在100×100的區(qū)域里，規(guī)則的布置有100個節(jié)點(diǎn)，圖4所示是網(wǎng)絡(luò)節(jié)點(diǎn)布局圖和OF0的拓?fù)浣Y(jié)構(gòu)，其中最左上側(cè)的0號節(jié)點(diǎn)為數(shù)據(jù)匯聚節(jié)點(diǎn)，右下側(cè)的49-99和94-98這11個節(jié)點(diǎn)為傳感器數(shù)據(jù)采集節(jié)點(diǎn)。數(shù)據(jù)從右下側(cè)的11個源節(jié)點(diǎn)發(fā)送到左上側(cè)的0號節(jié)點(diǎn)。由于該網(wǎng)絡(luò)具有對稱性，1和10對稱，2和20對稱等，對稱節(jié)點(diǎn)的能量消耗基本一致。本文中重點(diǎn)仿真了具有代表性的1、2、11、12、22這幾個關(guān)鍵節(jié)點(diǎn)的能量消耗情況。
對于OF0，由于跳數(shù)是路徑選擇的唯一標(biāo)準(zhǔn)，節(jié)點(diǎn)位置固定的網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)也相對保持不變。圖4即為這種情況下的拓?fù)浣Y(jié)構(gòu)。由圖4中可以看到，節(jié)點(diǎn)1和節(jié)點(diǎn)10承載了大部分的數(shù)據(jù)量，幾乎任何從下側(cè)或者右側(cè)源節(jié)點(diǎn)發(fā)過來的數(shù)據(jù)都要經(jīng)過這兩個節(jié)點(diǎn)轉(zhuǎn)發(fā)到Sink節(jié)點(diǎn)。而節(jié)點(diǎn)11，則只有來自源節(jié)點(diǎn)99的數(shù)據(jù)由它轉(zhuǎn)發(fā)。
圖5所示是系統(tǒng)節(jié)點(diǎn)能耗圖。其中圖5（a）為OF0方案下部分節(jié)點(diǎn)能量消耗圖。從圖中可以看出，最關(guān)鍵的節(jié)點(diǎn)1和節(jié)點(diǎn)10，能量很快就消耗殆盡。而節(jié)點(diǎn)11，則能耗相對較少。這對節(jié)點(diǎn)位置固定的網(wǎng)絡(luò)是很不利的，會使數(shù)據(jù)量較大的節(jié)點(diǎn)在短期內(nèi)能量迅速消耗完而死亡，而其他非位置關(guān)鍵節(jié)點(diǎn)，則一直被閑置。造成網(wǎng)絡(luò)能耗分布極其不均勻，能量利用率不高。
接下來可以仿真跳數(shù)和節(jié)點(diǎn)剩余能量相結(jié)合的路徑選擇方式，圖5（b）為跳數(shù)和能量按照2∶8的比例加權(quán)所得到的能耗結(jié)果。從圖5（b）可以看出，節(jié)點(diǎn)1、10和11的能耗更為均衡，第一個節(jié)點(diǎn)死亡的時間大為延長。跳數(shù)和節(jié)點(diǎn)剩余能量相結(jié)合的路徑選擇方式，能一定程度上改善以跳數(shù)為唯一度量所造成了能量消耗不均的情況，從而延長關(guān)鍵節(jié)點(diǎn)的生命長度。仿真中也能看到，最佳路徑的拓?fù)鋱D一直處于動態(tài)變化，原先經(jīng)過節(jié)點(diǎn)1和節(jié)點(diǎn)10到達(dá)匯聚節(jié)點(diǎn)的數(shù)據(jù)，有一部分從節(jié)點(diǎn)11分流，從而緩解節(jié)點(diǎn)1和節(jié)點(diǎn)10的壓力。
（a） HC路徑選擇方案節(jié)點(diǎn)能耗 （b） HC+EN路徑選擇方案節(jié)點(diǎn)能耗
本文也仿真了跳數(shù)（HC）和節(jié)點(diǎn)能量（EN）按照Lex的結(jié)合方式，即優(yōu)先考慮最小跳數(shù)，當(dāng)跳數(shù)相同的時候再考慮節(jié)點(diǎn)能量，以及在Add結(jié)合方式下按0.8HC+0.2EN和0.2HC+0.8EN的不同比例相結(jié)合的情況對比。最后得出的結(jié)論是，兩種不同的結(jié)合方式對網(wǎng)絡(luò)能耗均衡都有一定程度的改善；而Add的結(jié)合方式能耗更為均衡，且剩余能量所占的比例越高，改善的效果越為顯著。圖6所示是在不同路由策略下，關(guān)鍵節(jié)點(diǎn)能耗的對比情況。
4 結(jié) 語
本文描述了RPL協(xié)議的基本原理，并且對原路由協(xié)議的路徑選擇策略進(jìn)行了改進(jìn)，在只考慮跳數(shù)的基礎(chǔ)上，加入節(jié)點(diǎn)剩余能量的考慮，從而平衡了網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)整體壽命。由于RPL是近幾年新提出的協(xié)議，隨著實(shí)踐的不斷深入，越來越多的新問題被提出，還有很大的研究空間。RPL協(xié)議在物聯(lián)網(wǎng)領(lǐng)域有著廣闊的應(yīng)用前景，值得廣大學(xué)者進(jìn)一步深入研究。
5 致 謝
本論文的工作得到了實(shí)驗(yàn)室項(xiàng)目的大力支持。感謝國家自然科學(xué)基金（61271257），北京市自然科學(xué)基金（4122034）和教育部博士點(diǎn)基金（20120005110007）對本文研究工作的支持。
參 考 文 獻(xiàn)
[1] WINTER T. RFC6550 RPL： routing protocol for low power and lossy networks [S]. USA： Internet Engineering Task Force， 2012.
[2] VASSEUR J P， DUNKELS A.基于IP的物聯(lián)網(wǎng)架構(gòu)、技術(shù)與應(yīng)用[M]. ，田輝，徐貴保，譯.北京：人民郵電出版社，2011.
[3] DOHLER M. RFC 5548 routing requirements for urban low-power and lossy networks [S]. Internet Engineering Task Force， 2009.
[4] PISTER K. RFC5673 industrial routing requirements in low-power and lossy networks [S]. Internet Engineering Task Force， 2009.
[5] BRANDT A. RFC5826 home automation routing requirements in low-power and lossy networks[S]. Internet Engineering Task Force， 2010.
[6] MARTOCCI J. RFC5867 building automation routing requirements in low-power and lossy networks [S]. Internet Engineering Task Force， 2010.6
[7] LEVIS P. The trickle algorithm draft-ietf-roll-trickle-08 [S]. Internet Engineering Task Force， 2011.
[8] THUBERT P. RFC6552 objective function zero for the routing protocol for low-power and lossy networks （RPL） [S]. Internet Engineering Task Force， 2012.
[9] VASSEUR JP. RFC6551 routing metrics used for path calculation in low-power and lossy networks [S]. Internet Engineering Task Force， 2012.
[10]廖夢澤.無線傳感器網(wǎng)絡(luò)生命期最優(yōu)化[D].上海：上海交通大學(xué)，2010.
關(guān)鍵詞：移動Ad Hoc；NS2；延時；多路徑路由協(xié)議
中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2007)03-10681-03
1 引言
移動Ad Hoc 網(wǎng)絡(luò)又稱移動自組網(wǎng)、多跳網(wǎng)絡(luò)，它的特點(diǎn)是由結(jié)點(diǎn)移動引起的動態(tài)拓?fù)?、信道帶寬有限和結(jié)點(diǎn)有限的存儲能力。面臨的關(guān)鍵挑戰(zhàn)是在動態(tài)環(huán)境下能在花費(fèi)最小的情況下傳送信息，另外，對QoS 的支持也是一個重要的研究課題。目前存在的多數(shù)協(xié)議也都是路由表驅(qū)動或是源結(jié)點(diǎn)發(fā)起的按需路由協(xié)議，而且這些協(xié)議都是基于盡力服務(wù)模型的，無法滿足現(xiàn)近一些需要QoS路由的業(yè)務(wù)。在有線網(wǎng)的多路徑協(xié)議中，已經(jīng)對QoS路由有很廣泛的研究，但是這些研究并不能適用于Ad Hoc網(wǎng)絡(luò)的。其中文獻(xiàn)[1,2,3]詳細(xì)闡述了移動Ad Hoc網(wǎng)絡(luò)QoS路由協(xié)議的發(fā)展現(xiàn)狀，文獻(xiàn)[4,5]對移動Ad Hoc網(wǎng)絡(luò)中的QoS約束作出了深入解析，文獻(xiàn)[6,7,8]提出一些新的支持QoS約束的移動Ad Hoc路由協(xié)議，在本文中，我們將給出一種多路徑QoS路由協(xié)議MQDSR，該路由能夠支持QoS約束并提供多路徑路由以減少路由發(fā)現(xiàn)過程和路由維護(hù)。
2 DSR協(xié)議描述
DSR（Dynamic Source Routing）協(xié)議是一種基于源路由方式的按需路由協(xié)議。在DSR協(xié)議中，當(dāng)發(fā)送者發(fā)送報(bào)文時，在數(shù)據(jù)報(bào)文頭部攜帶到達(dá)目的節(jié)點(diǎn)的路由信息，該路由信息由網(wǎng)絡(luò)中的若干節(jié)點(diǎn)地址組成，源節(jié)點(diǎn)的數(shù)據(jù)報(bào)文就通過這些節(jié)點(diǎn)的中繼轉(zhuǎn)發(fā)到達(dá)目的節(jié)點(diǎn)。與基于表驅(qū)動方式的路由協(xié)議不同的是，在DSR協(xié)議中，節(jié)點(diǎn)不需要實(shí)時維護(hù)網(wǎng)絡(luò)的拓?fù)湫畔ⅰ?/p>
DSR路由協(xié)議主要由路由發(fā)現(xiàn)和路由維護(hù)兩部分組成。路由發(fā)現(xiàn)過程主要用于幫助源節(jié)點(diǎn)獲得到達(dá)目的節(jié)點(diǎn)的路由。當(dāng)路由中的節(jié)點(diǎn)由于移動、關(guān)機(jī)等原因無法保證到達(dá)目的節(jié)點(diǎn)時，當(dāng)前的路由就不再有效了。DSR協(xié)議通路由維護(hù)過程來監(jiān)測當(dāng)前路由的可用情況，當(dāng)監(jiān)測到路由故障時，將調(diào)用新的一輪路由發(fā)現(xiàn)過程。文獻(xiàn)[3]中詳細(xì)論述了DSR協(xié)議的路由發(fā)現(xiàn)及路由維護(hù)過程。
3 QoS參數(shù)的計(jì)算
隨著移動通信的不斷發(fā)展和多媒體業(yè)務(wù)的日益普及，在移動網(wǎng)絡(luò)上提供QoS保障的研究逐漸成為一個熱點(diǎn)。由于Ad Hoc網(wǎng)絡(luò)中結(jié)點(diǎn)的移動性和無線傳輸特性，導(dǎo)致對QoS約束的支持遠(yuǎn)比有線網(wǎng)中困難。本文中，我們把帶寬的計(jì)算和預(yù)留作為QoS參數(shù)計(jì)算的主要問題。在時隙的Ad Hoc網(wǎng)絡(luò)中，計(jì)算帶寬不僅需要得到路徑上鏈路可用帶寬信息，而且知道如何安排時隙，所以在Ad Hoc網(wǎng)絡(luò)中計(jì)算帶寬是一件很困難的事情，而且是一個NP-完全問題，在這種情況下，往往用啟發(fā)式路由算法來解決這種問題。在我們將要提出的MQDSR中，使用文獻(xiàn)[4]中的啟發(fā)式路由算法來計(jì)算和預(yù)留帶寬。
4 MQDSR協(xié)議描述
針對現(xiàn)在移動Ad Hoc網(wǎng)絡(luò)中的大多數(shù)單路徑協(xié)議，我們在DSR路由協(xié)議的基礎(chǔ)，提出了一種多路徑的QoS路由協(xié)議MQDSR。
4.1 路由的發(fā)現(xiàn)過程
當(dāng)一個源結(jié)點(diǎn)需要建立一條路由，但是還沒有目的地的路由信息時，它首先廣播一個QRP(QoS Route Probe)包到它的鄰接結(jié)點(diǎn)。當(dāng)一個結(jié)點(diǎn)收到QRP包時，它將對帶寬進(jìn)行計(jì)算，為了使用逐跳的方法計(jì)算可用帶寬，中間結(jié)點(diǎn)并不使用路由緩存去直接回復(fù)QRP包。下面給出了一個中間結(jié)點(diǎn)N處理QRP的算法的偽代碼：
IFCheckRedundantPkt(QRP.Source,QPR.QRPSN)||IncludedNodeList(QRP.Node_List,N))
DropAndExit(QRP)
AvailableBandwidth=ComputeBandwidth(QRP,N)
IF AdmissionDecision(AvailableBandwidth, QRP.Bmin)=0)
DropAndExit(QRP)
ELSE
QRP.TTL = QRP.TTLC1
IF QRP.TTL = 0
DropAndExit(QRP)
LogSlotInfo(QRP.Slot_List_Array)
AppendToNodelist(QRP.Node_List, N)
IF N! = QRP.Destination
Forward(QRP)
對于目的結(jié)點(diǎn)，當(dāng)收到第一個QRP包時，它會向源結(jié)點(diǎn)發(fā)送一個QRR（QoS Route Reply）包，同時保存第一個QRP包記錄的路由，然后，目的結(jié)點(diǎn)將等待消息ROUTE_WAIT，同時收集其它的QRP控制包。目的地可能接收多個QRP，每一個都代表著一個從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的可用的路由，我們采用了備份路由機(jī)制，因此可以用一個的選擇算法，在眾多路由當(dāng)中選取一個最佳的作為首選路由，選取另一條作為備份，該算法如下：
NodeDisjointRoute=FindNodeDisjointRoute()
IF NodeDisjointRoute = 0
LinkMaxDisjointRoute=FindMaxLinkDisjointRoute()
IF LinkMaxDisjointRoute > 1
SelectRoutewithMinHop()
ELSE IF NodeDisjointRoute > 1
SelectRoutewithMinHop()
接著目的結(jié)點(diǎn)發(fā)送其它的QRR到源結(jié)點(diǎn)。因此，我們可以得到兩條源結(jié)點(diǎn)到目的結(jié)點(diǎn)的路由。
中間結(jié)點(diǎn)通過QRR包來進(jìn)行資源的預(yù)留。如果源結(jié)點(diǎn)能接收到QRR包，一個端到端的資源預(yù)留將完成，同時，它會使用第一條建立的路由立即發(fā)送數(shù)據(jù)包。當(dāng)接收到第二個QRR包時，這時將有兩條源結(jié)點(diǎn)到目的結(jié)點(diǎn)的路由，MQDSR協(xié)議中采用的簡單的包分配機(jī)制，把數(shù)據(jù)流分配到兩條路由上進(jìn)行傳送數(shù)據(jù)，這樣可減少網(wǎng)絡(luò)負(fù)載。
4.2 路由維護(hù)
當(dāng)一個結(jié)點(diǎn)發(fā)現(xiàn)它到下游結(jié)點(diǎn)的鏈路失效后，它將發(fā)送一個MQRP_Route_Error包到源結(jié)點(diǎn)。從斷開的結(jié)點(diǎn)到源結(jié)點(diǎn)之間的路由上的所有結(jié)點(diǎn)，當(dāng)它們收到MQRP_Route_Error包時，將釋放預(yù)留的資源，同時丟棄隊(duì)列中所有的待發(fā)送的QoS請求包。當(dāng)源結(jié)點(diǎn)收到MQRP_Route_Error包時，它將刪所有使用斷鏈的路由條目。如果兩條路由中，僅僅只有一條路由失效，源結(jié)點(diǎn)將使用剩下的那條路由繼續(xù)發(fā)送數(shù)據(jù)。如果兩條路由都已失效，那么源結(jié)點(diǎn)將重新發(fā)起一次新的路由發(fā)現(xiàn)過程。
5 正確性驗(yàn)證及復(fù)雜性分析
定理1 由MQDSR選擇的路徑是無環(huán)的。
證明：假設(shè)p是一個以D為目的探測幀，而S(P, D)是路由算法選擇的路由，若S(P, D)中存在一個環(huán)路，則說明在路徑S(P, D)上存在一個節(jié)點(diǎn)i兩次收到了探測幀p并轉(zhuǎn)發(fā)p。這與DSR協(xié)議中規(guī)定的一個節(jié)點(diǎn)只能轉(zhuǎn)發(fā)一個探測幀矛盾。由于MQDSR遵循了DSR的該機(jī)制，因此S(P, D)必定是無環(huán)的。證畢。
定理2 在MQDSR協(xié)議的路由算法中，時間復(fù)雜性為O(2h)式中：h為Ad Hoc網(wǎng)絡(luò)中各條路徑中鏈路數(shù)量的最大值。
證明：在MQDSR協(xié)議的路由算法中，需要發(fā)送探測幀來建立路由，成功建立一條路徑需要花費(fèi)的時間開銷是一個來回的時間。假設(shè)消息每經(jīng)過一條鏈路花費(fèi)的時間開銷是一個單位，而假設(shè)h是被選擇的多路徑中鏈路數(shù)量的最大值，則MQDSR協(xié)議算法路徑建立的時間復(fù)雜性為O(2h)，證畢。
定理3 在MQDSR協(xié)議的路由算法中，消息的復(fù)雜性為O(3h)。式中：h為Ad Hoc網(wǎng)絡(luò)中各條路徑中鏈路數(shù)量的最大值。
證明：在MQDSR協(xié)議算法中，主要使用兩個報(bào)文Route Request和Route Reply來發(fā)現(xiàn)路由，由于本協(xié)議路徑數(shù)目為2，則每次連接的成功建立會有最多3個報(bào)文。假設(shè)h為Ad Hoc網(wǎng)絡(luò)中各條路徑中鏈路數(shù)量的最大值，則每個報(bào)文最多會經(jīng)歷h跳的轉(zhuǎn)發(fā)，所以報(bào)文消息復(fù)雜性為O(3h)。證畢。
6 訪真實(shí)驗(yàn)與分析
以下仿真是在NS2中進(jìn)行的，仿真環(huán)境及模型如下：
MAC層協(xié)議采用的是IEEE 802.11。無線電傳播模型是Two-Ray Ground Reflection Model，載頻是914MHz，帶寬為2M，天線采用OmniAntenna。
運(yùn)行場景：采用NS的setdest隨機(jī)產(chǎn)生。50個節(jié)點(diǎn)在一個1000×1000的矩形區(qū)域按照random waypoint模型移動。每個節(jié)點(diǎn)隨機(jī)的向一個目的地運(yùn)動，到達(dá)后，停留一段時間，繼續(xù)朝另一個方向移動，移動速度為3m/s到18m/s不等。
數(shù)據(jù)場景：信源用的是CBR（恒定比特率），包長512bytes。30個信源在仿真的過程中，在不同的時間開始發(fā)送數(shù)據(jù)包。
以下是實(shí)驗(yàn)中，不同結(jié)點(diǎn)移動速率下的DSR和MQDSR的對比圖：
圖1顯示了，在不同的節(jié)點(diǎn)移動速度級別下，MQDSR與DSR的分組投遞率的變化情況以及之間的差異。從中可以看出，當(dāng)節(jié)點(diǎn)移動速率越高時，兩個協(xié)議的性能總體上都有所下降，但另一方面，QMDSR比DSR有更好的分組投遞率，這是因?yàn)樵贒SR中，有較多的路由重建過程，網(wǎng)絡(luò)中產(chǎn)生了更多的數(shù)據(jù)包的沖突，而在MQDSR中，我們有兩條路徑可用，既使在其中一條無效的情況吧，還能用另外一條路徑繼續(xù)發(fā)送數(shù)據(jù)，所以在MQDSR協(xié)議的網(wǎng)絡(luò)擁有更好的吞吐量性能。
圖1 分組投遞率隨節(jié)點(diǎn)移動速率的變化情況
圖2中顯示了端到端的延時隨節(jié)點(diǎn)移動速率的變化情況，相比之下，MQDSR比DSR擁有更少的延時，這是因?yàn)椋贒SR中路由重建較頻繁產(chǎn)生了大量的延時，而數(shù)據(jù)包的等待也會產(chǎn)生大量的延時，但是在MQDSR中，因?yàn)槲覀冇袃蓷l路徑可用，既使在其中一條無效的情況吧，還能用另外一條路徑繼續(xù)發(fā)送數(shù)據(jù)，所以延時相對較少。
圖2 端到端的延時隨節(jié)點(diǎn)移動速率的變化情況
圖3顯示了路由控制負(fù)載情況，我們可以看到在節(jié)點(diǎn)低速率情況下，MQDSR比DSR的負(fù)載要稍大，這是因?yàn)镸QDSR在建立多路徑路由過程中，需要較多的控制報(bào)文，但是，隨著移動節(jié)點(diǎn)移動速率的增加，MQDSR的控制負(fù)載相對較少，這是因?yàn)镈SR協(xié)議將比MQDSR產(chǎn)生更多的路由重建過程，而在MQDSR協(xié)議僅當(dāng)兩條由源結(jié)點(diǎn)到目的結(jié)點(diǎn)的路由同時失效后，才會重新發(fā)起路由發(fā)現(xiàn)過程。
圖3 路由控制負(fù)載隨節(jié)點(diǎn)移動速率的變化情況
7 結(jié)束語
移動Ad Hoc網(wǎng)絡(luò)是一門新興研究領(lǐng)域，具有很高的實(shí)用價(jià)值，并具有極其廣泛的應(yīng)用前景。其中路由協(xié)議是移動Ad Hoc網(wǎng)絡(luò)的核心技術(shù)之一，同時也是熱門研究的對象。本文針對Ad Hoc網(wǎng)絡(luò)中DSR路由協(xié)議進(jìn)行了分析，結(jié)合多路徑路由算法思想，提出了多路徑QoS路由協(xié)議MQDSR，并進(jìn)行了仿真實(shí)驗(yàn)，仿真結(jié)果表明MQDSR路由協(xié)議在動態(tài)環(huán)境中擁有較好的性能。本論文中并沒有討論能量受限的問題，以及結(jié)點(diǎn)移動的預(yù)測問題，在今后的研究當(dāng)中，能量，移動預(yù)測等也是路由協(xié)議中重要一環(huán)。
參考文獻(xiàn)：
[1] 孫寶林, 李臘元. Ad Hoc網(wǎng)絡(luò)QoS多播路由協(xié)議[J]. 計(jì)算機(jī)學(xué)報(bào),2004,27(10):1402-1407.
[2] 李臘元，李春林. 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)[M]. 北京:國防工業(yè)出版社，2004.
[3] 肖小玲，李臘元，張翔. 移動Ad Hoc網(wǎng)絡(luò)QoS路由協(xié)議研究，計(jì)算機(jī)工程與應(yīng)用，2006.01.
[4] C.R.Lin and J. S. Liu Bandwidth routing in ad hoc wireless networks. In IEEE Globecom, 1998.
[5] C.-R. Lin and J. S. Liu. "QoS Routing in Ad Hoc Wireless networks," IEEE Journal on Selected Areas in Communications, 1999,17(8):1426-1438.
[6] K.N.S.Chen.Distributed quality-of-service routing in ad hoc networks.IEEE Journal on Selected Area in Communications, 1999,17(8):1488-1505.
[7] R.Sivakumar, P.Sinha, and C.Bharghavan, V.a core-extraction distributed ad hoc routing algorithm.Selected Areas in Communications, IEEE Journal on, 1999,17(8):1454-1465.
關(guān)鍵詞：傳感器；無線傳感器；網(wǎng)絡(luò)路由協(xié)議；平面路由協(xié)議；層次路由協(xié)議
一、引言
近年來，隨著現(xiàn)代化科技的蓬勃發(fā)展，無線傳感器技術(shù)也越來越受到人們的關(guān)注和重視。無線傳感器網(wǎng)絡(luò)，主要由傳感節(jié)點(diǎn)、終端節(jié)點(diǎn)和觀察對象等三個部分組成。就目前來看，無線傳感器網(wǎng)絡(luò)在醫(yī)療監(jiān)護(hù)、社區(qū)監(jiān)控、礦井生產(chǎn)及軍事偵探等多個領(lǐng)域的應(yīng)用正日趨廣泛。無線傳感器網(wǎng)絡(luò)路由協(xié)議，作為無線傳感器網(wǎng)絡(luò)中的關(guān)鍵技術(shù)，通過對其基本特征和設(shè)計(jì)要求，以及平面路由協(xié)議和層次路由協(xié)議等兩大分類的認(rèn)識和了解，對于無線傳感器技術(shù)的發(fā)展和變革有著不容忽視的促進(jìn)作用。
二、無線傳感器網(wǎng)絡(luò)路由協(xié)議
1.無線傳感器網(wǎng)絡(luò)路由協(xié)議的特點(diǎn)
無線傳感器網(wǎng)絡(luò)路由協(xié)議，主要是用來處理網(wǎng)絡(luò)中的傳輸數(shù)據(jù)，在無線傳感器網(wǎng)絡(luò)中充當(dāng)著極為重要的角色。通過對無線傳感器網(wǎng)絡(luò)路由協(xié)議的分析，認(rèn)為其具有以下幾點(diǎn)鮮明特點(diǎn)和局限性。
（1）終端節(jié)點(diǎn)的特點(diǎn)。傳感器的節(jié)點(diǎn)數(shù)量相對較大，促使其能夠作用于計(jì)算子系統(tǒng)、通信子系統(tǒng)、傳感子系統(tǒng)和能量供應(yīng)子系統(tǒng)等多個方面，不過同時也加大了建立全局地址的難度，而且各節(jié)點(diǎn)的傳輸能力、處理能力和存儲能力也極為有限。
（2）傳感器定位特點(diǎn)。在無線傳感器中，由于終端節(jié)點(diǎn)的數(shù)量龐大，且通常是數(shù)據(jù)聚集的主要地方，因此，在進(jìn)行傳感器定位上，主要工作是由終端節(jié)點(diǎn)來完成的。
（3）傳感器網(wǎng)絡(luò)特點(diǎn)。根據(jù)不同的應(yīng)用場景，傳感器網(wǎng)絡(luò)的作用類型也不同。呈現(xiàn)功能多樣化的特點(diǎn)。
2.無線傳感器網(wǎng)絡(luò)路由協(xié)議的設(shè)計(jì)
（1）注重路由算法節(jié)能。在無線傳感器網(wǎng)絡(luò)路由協(xié)議的設(shè)計(jì)上，降低路由算法的耗能，在網(wǎng)絡(luò)周期運(yùn)行、通信功能等方面起著決定性的作用。通過降低算法能量消耗，能夠有效延長網(wǎng)絡(luò)的生命周期。
（2）注重路由算法擴(kuò)展。隨著無線傳感器的應(yīng)用日趨廣泛，終端節(jié)點(diǎn)的數(shù)量也在不斷增加，給網(wǎng)絡(luò)造成了一定程度的繁冗。為此，在設(shè)計(jì)時注重路由算法擴(kuò)展性的提高，能夠有效地融合新節(jié)點(diǎn)，從而提高網(wǎng)絡(luò)處理數(shù)據(jù)的能力，延長使用壽命。
（3）注重路由算法容錯。注重路由算法容錯能力的提高，能夠保證在分層結(jié)構(gòu)的終端節(jié)點(diǎn)失效時，最大限度減輕簇頭的高負(fù)載，以免整個網(wǎng)絡(luò)陷入癱瘓。
3.要求數(shù)據(jù)融合
通過強(qiáng)化數(shù)據(jù)的融合，能夠減少無線傳感器在采集和傳遞數(shù)據(jù)方面造成的大量冗余信息，確保網(wǎng)絡(luò)系統(tǒng)的簡潔和信息的精確。
4.無線傳感器網(wǎng)絡(luò)路由協(xié)議的類別及分析
根據(jù)不同的角度，無線傳感器網(wǎng)絡(luò)路由協(xié)議可以劃分的類別也不同。通過路由發(fā)現(xiàn)策略，可以分為主動路由和被動路由，而從邏輯結(jié)構(gòu)出發(fā)，則可以劃分成平面路由協(xié)議和層次路由協(xié)議等兩種。
（1）平面路由協(xié)議。
擴(kuò)散法。即傳統(tǒng)的網(wǎng)絡(luò)路由協(xié)議，是通過源節(jié)點(diǎn)將網(wǎng)絡(luò)數(shù)據(jù)副本傳輸給相鄰節(jié)點(diǎn)，相鄰節(jié)點(diǎn)又將其發(fā)送給下一相鄰節(jié)點(diǎn)，以此來達(dá)到數(shù)據(jù)擴(kuò)散并最終將數(shù)據(jù)傳輸給目標(biāo)節(jié)點(diǎn)的方法。具有簡單實(shí)現(xiàn)、降低網(wǎng)絡(luò)拓?fù)湫畔⒁约奥酚伤惴ㄏ牡哪茉?，且能夠適用于要求較高的場合等優(yōu)勢，但從另一個角度來看，這種擴(kuò)散法很可能會造成信息爆炸、重疊發(fā)送信息及盲目使用資源等現(xiàn)象。
SPIN協(xié)議。是基于節(jié)點(diǎn)間的協(xié)商制度和資源自適應(yīng)機(jī)制研發(fā)出來的通信路由協(xié)議，用于處理擴(kuò)散法中的缺陷。通過在傳輸數(shù)據(jù)過程中，節(jié)點(diǎn)與節(jié)點(diǎn)之間的協(xié)商，能夠保證傳輸?shù)臄?shù)據(jù)的可靠性和可用性。
定向擴(kuò)散。是采用梯度的形式，對節(jié)點(diǎn)傳輸數(shù)據(jù)方向進(jìn)行搜索，以此來獲得匹配數(shù)據(jù)的新協(xié)議。運(yùn)行的終端節(jié)點(diǎn)主要用命名機(jī)制來描述數(shù)據(jù)，并通過向所有節(jié)點(diǎn)發(fā)送被命名數(shù)據(jù)的任務(wù)描述符，從而實(shí)現(xiàn)數(shù)據(jù)的采集。相對來說，這種定向擴(kuò)散協(xié)議，在節(jié)能和擴(kuò)展方面具有更大的優(yōu)勢。
（2）層次路由協(xié)議。
LEACH協(xié)議。通過采用聚類的形式發(fā)展起來的LEACH路由協(xié)議，能夠不斷隨機(jī)循環(huán)執(zhí)行聚類首節(jié)點(diǎn)重構(gòu)過程，以此來實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)中能量負(fù)載均衡分配。其重構(gòu)過程主要分為類準(zhǔn)備階段和就緒階段等兩部分。通過延長就緒階段的時間，同時縮短類準(zhǔn)備階段的用時，能夠有效地節(jié)省資源，進(jìn)而提高整個網(wǎng)絡(luò)生存的時長到15%。
PEGAGIS協(xié)議。是基于LEACH協(xié)議設(shè)計(jì)的，并在假定終端節(jié)點(diǎn)的同構(gòu)和靜止的前提下，通過終端節(jié)點(diǎn)發(fā)送能量遞減的測試信號來找出相鄰最近節(jié)點(diǎn)。從而明確各節(jié)點(diǎn)之間的位置關(guān)系，并通過選擇所屬聚類來完成到sink的鏈路優(yōu)化。不但促使整個網(wǎng)絡(luò)的生存時間是LEACH的兩倍左右，同時由于融合數(shù)據(jù)降低了收發(fā)次數(shù)，進(jìn)而節(jié)省了系統(tǒng)能源。不過對于鏈中遠(yuǎn)距離的節(jié)點(diǎn)，則較為容易引起數(shù)據(jù)延遲。
TEEN協(xié)議。該協(xié)議的主要特點(diǎn)是實(shí)時性，是基于LEACH的聚類結(jié)構(gòu)及其運(yùn)行模式，采用硬、軟閾值來發(fā)送檢測數(shù)據(jù)的協(xié)議。新硬閾值是由監(jiān)測數(shù)據(jù)首次超過設(shè)定硬閾值時確定的。當(dāng)節(jié)點(diǎn)發(fā)送的硬閾值變化幅度大于軟閾值界定范圍，則節(jié)點(diǎn)重新采集數(shù)據(jù)設(shè)定硬閾值。同時，節(jié)點(diǎn)能夠通過調(diào)節(jié)軟閾值大小，有效平衡監(jiān)測精度與系統(tǒng)能耗。TEEN協(xié)議的實(shí)時性，促使其能快速反應(yīng)并處理突發(fā)事件，但受其自身限制，該協(xié)議并不適合持續(xù)采集數(shù)據(jù)的應(yīng)用環(huán)境。
通過對無線傳感器網(wǎng)絡(luò)路由協(xié)議相關(guān)知識點(diǎn)的分析和思考，能夠進(jìn)一步加深人們對無線傳感器網(wǎng)絡(luò)的研究，推動該技術(shù)在國內(nèi)相關(guān)領(lǐng)域的普及和發(fā)展。
參考文獻(xiàn)：
【關(guān)鍵詞】無線傳感網(wǎng)絡(luò) 分簇 多跳路由算法 移動性
1 引言
傳感器在計(jì)算和無線通訊中廣泛使用，如監(jiān)測外部環(huán)境，把感知的數(shù)據(jù)轉(zhuǎn)化為用戶可以理解的信息。傳感網(wǎng)絡(luò)的應(yīng)用是目前國際科學(xué)研究的熱點(diǎn)。隨著社會的發(fā)展，在很多的移動環(huán)境應(yīng)用了無限傳感器，如海洋的監(jiān)測、移動車輛的監(jiān)測、動物的監(jiān)測等，因此研究移動環(huán)境下的無線傳感器網(wǎng)絡(luò)越來越重要[1-2]。
傳感器網(wǎng)絡(luò)的移動性帶來了許多問題。如傳感器節(jié)點(diǎn)在成功部署之后由于節(jié)點(diǎn)的移動隨時變換位置，很容易造成拓?fù)涞淖兓?；通信鏈路建立之后，?jié)點(diǎn)移動很容易偏離最初的位置，從而導(dǎo)致連接斷裂、路由中斷；節(jié)點(diǎn)移動造成數(shù)據(jù)延遲發(fā)送；節(jié)點(diǎn)的移動造成路由建立的頻率增大，從而增大能量的消耗，縮短了網(wǎng)絡(luò)生存時間。因此針對移動環(huán)境設(shè)計(jì)支持移動性的路由協(xié)議十分必要。
基于分簇的路由協(xié)議有很多。LEACH[3]的成簇思想貫穿于其后發(fā)展出的很多分簇路由協(xié)議中，如TEEN[4]、PEGASIS[5]、APTEEN[6]都基于分簇的路由協(xié)議，但在移動性的支持上存在不足，尤其當(dāng)網(wǎng)絡(luò)規(guī)模增大時，缺陷就更加明顯。M-LEACH[7]是基于LEACH提出的支持簇頭和成員節(jié)點(diǎn)的移動協(xié)議，簇頭選取時考慮了節(jié)點(diǎn)剩余能量、位置及節(jié)點(diǎn)的移動速率，但沒有在簇的建立階段解決移動性問題。EMHR[8]算法是簇頭在數(shù)據(jù)傳輸時可以通過多跳傳輸，根據(jù)權(quán)值確定下一跳簇頭，這樣EMHR協(xié)議在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中平衡負(fù)載和降低簇頭能量消耗，此協(xié)議主要是針對靜態(tài)網(wǎng)絡(luò)。
分簇技術(shù)可以避免感知節(jié)點(diǎn)之間的信息傳輸，通過簇頭數(shù)據(jù)融合，減少數(shù)據(jù)冗余，減少發(fā)送數(shù)據(jù)量，降低能耗，更好地支持移動性。多跳傳輸技術(shù)是動態(tài)自組織，利用網(wǎng)絡(luò)中的節(jié)點(diǎn)動態(tài)建立和維持網(wǎng)絡(luò)連接。由于多跳技術(shù)的獨(dú)特性，無線傳感網(wǎng)絡(luò)多跳技術(shù)得到了極大的關(guān)注，大量信息表明多跳路由協(xié)議的能耗遠(yuǎn)低于單跳路由協(xié)議。針對現(xiàn)有分簇路由中存在的缺陷，本文提出新的支持移動的簇頭多跳路由算法，以降低能耗。
2 EM-CHMR算法
基于LEACH-M算法，在感知節(jié)點(diǎn)移動且基站（BS）不移動的環(huán)境下，根據(jù)節(jié)點(diǎn)的移動信息進(jìn)行分簇，分簇成功之后建立高效的多跳路徑，筆者提出能有效地支持移動性的簇頭多跳路由策略（EM-CHMR，Energy-efficient Mobile Cluster Head Multi-hops Routing protocol）。此路由策略中，簇首向基站傳輸數(shù)據(jù)引入了多跳路由機(jī)制，讓距基站較近的簇首適當(dāng)承擔(dān)一些數(shù)據(jù)中繼轉(zhuǎn)發(fā)任務(wù)，把直接長距離通信變成間接的多次短距離通信，在支持移動下保證轉(zhuǎn)發(fā)簇首有充分的能量來進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。
2.1 分簇的模型
簇頭多跳的簡單模型如圖1，模型中距離BS較遠(yuǎn)的簇頭可以通過建立多跳路徑與BS通信，這樣可以降低自身的能量消耗。同時距離BS較近的簇頭不需要再進(jìn)行多跳，可以直接與BS進(jìn)行通信。模型中感知節(jié)點(diǎn)和簇頭都可以進(jìn)行移動，但是BS是固定位置不移動；每個節(jié)點(diǎn)的移動速度大小都限制在一定范圍內(nèi)；節(jié)點(diǎn)同構(gòu)，且初始能量相同；傳感器節(jié)點(diǎn)得到的信息，可以使用GPS或其他位置檢測方案；傳感器節(jié)點(diǎn)的發(fā)射功率可以進(jìn)行調(diào)節(jié)。
路由算法中利用文獻(xiàn)[9]提出的能量消耗模型，節(jié)點(diǎn)發(fā)射kbit數(shù)據(jù)到距離為d的位置消耗的能量為：
其中，Eelec表示發(fā)端電路運(yùn)算和處理每比特?cái)?shù)據(jù)的能耗；εfs和εmp為放大器的系數(shù)；d0為臨界距離。
2.2 簇頭的選取
簇頭選取算法是基于M-LEACH協(xié)議提出的，網(wǎng)絡(luò)模型是一個均勻的網(wǎng)絡(luò)，簇頭的數(shù)量確定方式與M-LEACH相同。根據(jù)簇頭數(shù)量把整個區(qū)域劃分為子區(qū)域，然后為每個區(qū)域選取簇頭。首先按照剩余能量利用閾值Eselect進(jìn)行篩選，避免節(jié)點(diǎn)剩余能量不足造成早死現(xiàn)象。為了讓簇頭均勻分布并對整個傳感網(wǎng)絡(luò)實(shí)現(xiàn)完全覆蓋，把整個區(qū)域分成M個子區(qū)域，在每一個子區(qū)域中選取一個簇頭。假設(shè)第j子區(qū)域節(jié)點(diǎn)數(shù)Nj，每個節(jié)點(diǎn)坐標(biāo)為（xi，yj），速度為vi。簇頭的最佳位置S0計(jì)算方式如下：
移動方向用θi（0O≤θi≤180O）表示，意為節(jié)點(diǎn)i的移動方向和連接節(jié)點(diǎn)指向最佳位置的直線形成的夾角（速度和直線的最小夾角）。最佳選擇則是節(jié)點(diǎn)移動方向是S0，即夾角越小越好。角度則是處理后的角度，其中θt是角度閾值。
如果簇頭移動速度過快則容易造成簇的破壞，移動速度慢則適合整個網(wǎng)絡(luò)的移動速度。式（4）表示節(jié)點(diǎn)i處理后的速度，其中vt是速度閾值，vi為節(jié)點(diǎn)i的速度。
節(jié)點(diǎn)i為簇頭的代價(jià)函數(shù)為：
由式（5）看到，、和變小時值也變小，則是節(jié)點(diǎn)i的速度因子，因此最小的節(jié)點(diǎn)為簇頭最理想的節(jié)，若存在多個節(jié)點(diǎn)，取最小值。
2.3 簇的形成
簇的形成階段，就是在感知節(jié)點(diǎn)選擇簇頭鍵入，并在其中形成簇。簇頭和感知節(jié)點(diǎn)的移動使得節(jié)點(diǎn)與簇頭位置關(guān)系的變化很難計(jì)算。為了降低復(fù)雜性，把速度大小和速度方向一起分析，利用速度和角度得到速度因子。
其中，vi根據(jù)閾值計(jì)算，θi是感知節(jié)點(diǎn)移動方向與連接感知節(jié)點(diǎn)、簇頭間直線所形成的夾角，θ0是簇頭移動方向和連接簇頭、感知節(jié)點(diǎn)的直線所形成的夾角?？梢钥闯?，移動因子不是兩個速度的矢量和，而是要考慮到兩個速度的移動方向變化，才能夠簡單高效地對節(jié)點(diǎn)移動性進(jìn)行評估。
基于EECS[10]協(xié)議，本文提出新的通信代價(jià)函數(shù)：
其中E=En_init/En_current，w是具體環(huán)境決定的權(quán)值，CHi是區(qū)域i的簇頭，BS為基站，d是距離，f是兩者之間的通信代價(jià)，EX為期望。Si為感知節(jié)點(diǎn)。Cost（i，j）表示成員節(jié)點(diǎn)i到簇頭j的通信代價(jià)，在簇的形成過程中，每個成員節(jié)點(diǎn)選取通信代價(jià)最小的簇頭加入簇區(qū)域。
2.4 多跳路徑建立
在數(shù)據(jù)傳輸中選擇下一跳的簇頭，對簇頭能量消耗有重要的影響。如果BS在簇頭傳輸?shù)挠行Х秶鷥?nèi)，簇頭將直接與BS進(jìn)行通信，否則通過其他簇頭進(jìn)行多跳傳輸。
為了多跳能量消耗，計(jì)算通過簇頭跳一次的情況，即從簇頭i到j(luò)再到BS。設(shè)簇頭i和j的距離為d（i，j），j和BS的距離為d（j，S）。根據(jù)無線通信能量消耗模型，總的能量消耗模型ET為：
可看出能量消耗的影響因素為d（i，j）和d（j，S），所以，簇頭i發(fā)送消息經(jīng)過n個簇頭到BS的能量消耗為：
式（10）充分體現(xiàn)了距離對簇頭能量的消耗的影響，因此可用距離的平方和作為權(quán)值函數(shù)的一個重要因素。
由于無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)是移動狀態(tài)，尤其在簇頭多跳網(wǎng)絡(luò)中，簇頭的移動很容易對多跳路徑造成破壞，因此在多跳路徑建立過程中要選取一條比穩(wěn)定且受速度影響較少的路徑。在簇頭多跳路徑中簇頭的移動可以縮短整個路徑的距離，也有可能使得路徑遭到破壞。
由圖2看到簇頭H0經(jīng)過（H1， H2， H3）到達(dá)基站BS，（S1， S2， S3）分別為簇頭到直線OS的距離，θ為H3移動方向與S3形成的角度。在多跳路徑中最好的效果是三個簇頭向OS移動，并且三個簇頭和OS的距離波動不要太大，因?yàn)椴▌舆^大會造成傳輸距離加大。因此要（0， S1， S2， S3， 0）（前后兩個0分為H0和BS到OS的距離）的方差來衡量節(jié)點(diǎn)的波動，它們的期望衡量嚴(yán)重偏離OS的大小。由于節(jié)點(diǎn)的移動造成簇頭位置的不斷變化，為了較好地反應(yīng)簇頭的移動，要充分考慮簇頭節(jié)點(diǎn)的移動速度大小和方向。Si在OS左面值為正，右面值為負(fù)。角度則是指向OS的銳角，反向?yàn)殁g角。當(dāng)多跳經(jīng)過簇頭數(shù)為n時，計(jì)算（Si+vitcosθ）的期望：
計(jì)算對應(yīng)方差：
其中t是根據(jù)輪到時間設(shè)定的值，設(shè)為半個輪時間。則新的權(quán)值函數(shù)如下：
Ei_residual是簇頭i的剩余能量，Ei_init是初始化能量。為了控制σ和es值極端情況（只等于0），約束如下：
在簇頭選取成功時，向周圍廣播信息通知普通節(jié)點(diǎn)，每一個簇頭會接收到周圍相鄰的信息，信息包括ID、移動信息、剩余能量等。每個簇頭把周圍的信息進(jìn)行存儲，然后根據(jù)收集的鄰居節(jié)點(diǎn)找出到BS的所有路徑，利用權(quán)值函數(shù)（11）進(jìn)行計(jì)算，權(quán)值最小的路徑的第二個簇頭作為下一跳節(jié)點(diǎn)。利用此算法，簇頭都可以找到下一跳節(jié)點(diǎn)。如果某簇頭能量不足作為多跳節(jié)點(diǎn)時，就向周圍發(fā)送取消作為多跳節(jié)點(diǎn)的信息，周圍簇頭把該節(jié)點(diǎn)記錄信息取消，從新選取下跳節(jié)點(diǎn)。
3 實(shí)驗(yàn)結(jié)果
實(shí)驗(yàn)無線傳感器網(wǎng)絡(luò)有100個感知節(jié)點(diǎn)組成，分布在100m*100m的區(qū)域中，基站BS隨機(jī)放在此區(qū)域中。速度范圍為（0， 2）m/s，速度閾值為0.3m/s，角度閾值為10o，方差和期望的閾值為1，相關(guān)參數(shù)如表1：
圖3表示隨著時間延長，感知節(jié)點(diǎn)逐漸出現(xiàn)了死亡現(xiàn)象，EM-CHMR協(xié)議的死亡節(jié)點(diǎn)出現(xiàn)較晚，兩種節(jié)點(diǎn)死亡數(shù)量在300s之后大量出現(xiàn)。在600s之后新協(xié)議的存活節(jié)點(diǎn)數(shù)量明顯高于M-LEACH協(xié)議的節(jié)點(diǎn)存活數(shù)量，表明簇頭多跳網(wǎng)絡(luò)較好地均衡了簇之間的能量，降低了感知節(jié)點(diǎn)的死亡數(shù)量。
圖4展示了能量消耗，可以明顯看出M-LEACH能量已經(jīng)消耗遠(yuǎn)高于EM-CHMR，在900s時M-LEACH能量消耗完畢，而EM-CHMR還有能量剩余，從而有效地延長了網(wǎng)絡(luò)生存時間。能量消耗和存活節(jié)點(diǎn)數(shù)量的變化充分體現(xiàn)了支持移動的簇頭多跳路由協(xié)議能夠較好支持移動，平衡節(jié)點(diǎn)能量，降低能耗，延長整個網(wǎng)絡(luò)的存活時間。
4 結(jié)束語
本文針對無線傳感器網(wǎng)絡(luò)的移動性，基于LEACH提出了EM-CHMR路由算法，保持了按輪進(jìn)行分簇，對簇頭節(jié)點(diǎn)采用了多跳算法，提出了信息權(quán)值函數(shù)及建立多跳路徑算法。仿真結(jié)果證明該方案支持移動的簇頭多跳路由策略，使得能量消耗均衡地分布在各節(jié)點(diǎn)上，保證了數(shù)據(jù)盡快地傳輸?shù)交?，彌補(bǔ)單跳的不足，從而使網(wǎng)絡(luò)壽命得到延長。支持移動的簇頭多跳路由協(xié)議的維護(hù)機(jī)制對簇和路徑的生存時間有很大的影響，因此，為了使移動傳感網(wǎng)絡(luò)中更好地降低能耗，還需要在路由維護(hù)機(jī)制方面展開更深一步的研究。
參考文獻(xiàn)：
[1] AKYILDIZ L F， SU WEILIAN， CIRCI E. A survey on Sensor networks[J]. IEEE Communications Magazine， 2002，40（8）： 102-114.
[2] YICK J， MUKHERJEE B， GHOSAL D. Wireless sensor network survey[J]. Computer Networks， 2008，52（12）： 2292-2330.
[3] HEINZELMAN W R ， CHANDRAKASAN A， BALAKRISHNAN H. Energy-efficient communication protocol for wireless micro-sensor networks[C]. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences（HICSS）， Maui， HI， 2000： 1-10.
[4] MANJESHWAR A， AGRAWAL D P. TEEN： a routing protocol for enhanced efficiency in wireless sensor networks[C]. Parallel and Distributed Processing Symposium， Proceedings 15th International， 2001： 2009-2015.
[5] LINDSEY S， RAGHAVENDRA C S. PEGASIS： power efficient gathering in sensor information systems[C]. Aerospace Conference Proceedings， 2002： 1125-1130.
[6] MANJESHWAR A， AGRAWAL D P. APTEEN： a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks. Parallel and Distributed Processing Symposium[C]. Proceedings of the International， 2002： 195-202.
[7] LAN TIEN NGUYEN， DEFAGO X， BEURAN R， et al. An Energy Efficient Routing Scheme for Mobile Wireless Sensor Networks[C]. Proceedings of the 2008 IEEE international symposium on wireless communication systems （ISWCS）， 2008： 568-572.
[8] HUANG WEN WEN， PENG YA LI， WEN JIA， et al. Energy-Efficient Multi-hop Hierarchical Routing Protocol for Wireless Sensor Networks[C]. 2009 International Conference on Networks Security Wireless Communications and Trusted Computing， 2009： 469-472.