吳 院

(深圳清華大學(xué)研究院 EDA重點(diǎn)實(shí)驗(yàn)室，深圳 518057)

?

移動(dòng)自組網(wǎng)中路由協(xié)議的分析與研究

吳 院

(深圳清華大學(xué)研究院 EDA重點(diǎn)實(shí)驗(yàn)室，深圳 518057)

移動(dòng)自組網(wǎng)是一種由具有自配置功能的移動(dòng)設(shè)備通過無線連接方式組成的網(wǎng)絡(luò)。近幾年來，對無線自組網(wǎng)各方面的研究十分突出，尤其是在災(zāi)難救援和執(zhí)法等領(lǐng)域。一個(gè)自然而然的想法就是，將基于位置的操作引進(jìn)到無線自組網(wǎng)中。在各種應(yīng)用中，節(jié)點(diǎn)的身份認(rèn)證事實(shí)上往往不如節(jié)點(diǎn)的位置有用。在可疑的無線自組網(wǎng)中，節(jié)點(diǎn)之間甚至不能信任彼此，因此它們的身份必須隱藏。本文將對移動(dòng)自組網(wǎng)中的路由協(xié)議進(jìn)行研究和對比。

位置；移動(dòng)自組網(wǎng)；路由；安全

引 言

移動(dòng)自組網(wǎng)(MANET)是由移動(dòng)無線設(shè)備組成的自配置動(dòng)態(tài)網(wǎng)絡(luò)。網(wǎng)絡(luò)中的節(jié)點(diǎn)能夠獨(dú)立地向各個(gè)方向移動(dòng)。節(jié)點(diǎn)之間的拓?fù)浣Y(jié)構(gòu)和鏈路經(jīng)常發(fā)生變化。移動(dòng)自組網(wǎng)允許用戶交換信息而不用考慮它們變動(dòng)的基礎(chǔ)設(shè)施。移動(dòng)自組網(wǎng)在災(zāi)難救援、商業(yè)和個(gè)人局域網(wǎng)等領(lǐng)域有大量的應(yīng)用。

路由就是指數(shù)據(jù)包從一個(gè)網(wǎng)絡(luò)傳送到另一個(gè)網(wǎng)絡(luò)或從網(wǎng)絡(luò)中的一個(gè)主機(jī)節(jié)點(diǎn)傳送到另一個(gè)主機(jī)節(jié)點(diǎn)的過程。路由功能主要由專門配置的路由器節(jié)點(diǎn)承擔(dān)，常常與橋接技術(shù)相混淆?；诰W(wǎng)絡(luò)結(jié)構(gòu)，路由策略可分為平面路由、層次路由和基于地理位置的路由(地理位置輔助路由)[1]。先驗(yàn)式(表驅(qū)動(dòng)路由)和反應(yīng)式(按需路由)協(xié)議屬于平面路由，在表驅(qū)動(dòng)路由下每個(gè)節(jié)點(diǎn)都擁有網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的路由信息，并且當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)更新路由信息。每個(gè)節(jié)點(diǎn)將路由信息存儲(chǔ)在路由表中。反應(yīng)式協(xié)議只有當(dāng)節(jié)點(diǎn)之間需要路由請求和應(yīng)答時(shí)才會(huì)建立路由?；旌蠀f(xié)議就是為了融合先驗(yàn)式和反應(yīng)式協(xié)議的優(yōu)缺點(diǎn)。

本文將從基本的、基于地理位置的和基于安全的路由協(xié)議的分類出發(fā)，對移動(dòng)自組網(wǎng)的路由協(xié)議進(jìn)行一個(gè)粗略的研究，主要側(cè)重于各協(xié)議優(yōu)缺點(diǎn)的分析。

1 移動(dòng)自組網(wǎng)路由協(xié)議的研究

1.1 基本的路由協(xié)議

(1) 鏈路狀態(tài)路由協(xié)議(LSR)

LSR[2]是一個(gè)基本的先驗(yàn)式路由協(xié)議，根據(jù)當(dāng)前條件發(fā)現(xiàn)路由，由Dijkstra提出的最短路徑優(yōu)先算法發(fā)展而來，其中每個(gè)節(jié)點(diǎn)都擁有整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖。網(wǎng)絡(luò)中的所有節(jié)點(diǎn)定期更新網(wǎng)絡(luò)拓?fù)鋱D，建立一個(gè)直連鏈路狀態(tài)數(shù)據(jù)包，并廣播給鄰居節(jié)點(diǎn)。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)廣播從它的鄰居節(jié)點(diǎn)接收到的鏈路狀態(tài)數(shù)據(jù)包，直到每個(gè)節(jié)點(diǎn)都有相同的路由信息。節(jié)點(diǎn)記錄下從其他節(jié)點(diǎn)收到的鏈路狀態(tài)信息，由此建立拓?fù)浣Y(jié)構(gòu)圖，從而找到其他節(jié)點(diǎn)的最佳路徑。

LSR收斂速度較快，并且能讓節(jié)點(diǎn)擁有整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖。但是它對存儲(chǔ)、CPU處理速度和網(wǎng)絡(luò)帶寬的需求較高。

(2) 目標(biāo)序列距離矢量路由協(xié)議(DSDV)

DSDV是一種先驗(yàn)式路由協(xié)議，它通過在路由表項(xiàng)里增加序列號，解決了距離矢量路由中的回路問題。與鏈路狀態(tài)協(xié)議不同的是，它不能獲得整個(gè)網(wǎng)絡(luò)的拓?fù)鋱D，然而它能容忍網(wǎng)絡(luò)內(nèi)部或網(wǎng)絡(luò)之間拓?fù)浣Y(jié)構(gòu)的快速變化。每個(gè)節(jié)點(diǎn)維護(hù)著到所有已知的目標(biāo)節(jié)點(diǎn)的路由信息，并定期更新。在路由選擇時(shí)，通常選取擁有最高序列號的路徑，在具有相同序列號的情況下，選擇具有最高度量值的路徑。DSDV[3]開銷很大，即使網(wǎng)絡(luò)拓?fù)錄]有發(fā)生變化，也要存儲(chǔ)那些不再使用的路徑信息。

DSDV對拓?fù)浣Y(jié)構(gòu)的改變反應(yīng)迅速，并能確保沒有路由回路。它的主要缺點(diǎn)是，大部分的路由信息從不使用，從而開銷很大。

(3) 按需平面距離矢量路由協(xié)議(AODV)

AVOD是一種反應(yīng)式路由協(xié)議，它僅在需要時(shí)才去發(fā)現(xiàn)到某個(gè)特定目標(biāo)的路由，并維護(hù)這一路由信息。AVOD[4]優(yōu)于DSR，它能減少在網(wǎng)絡(luò)中傳送的數(shù)據(jù)包報(bào)頭的大小，并且擁有路由表。AVOD效仿路由發(fā)現(xiàn)和路由維護(hù)階段通過路由請求和路由回復(fù)消息。源節(jié)點(diǎn)大量發(fā)出路由請求消息，網(wǎng)絡(luò)中的其他節(jié)點(diǎn)轉(zhuǎn)播這個(gè)請求，從而形成反過來指向這一源節(jié)點(diǎn)的路徑，當(dāng)預(yù)期的目標(biāo)節(jié)點(diǎn)收到此消息時(shí)，它就會(huì)回復(fù)一條路由回復(fù)消息給源節(jié)點(diǎn)。

AVOD協(xié)議減少了控制信息的開銷，并且對網(wǎng)絡(luò)拓?fù)涞母淖兎磻?yīng)迅速。其主要缺點(diǎn)是，只有在低擁塞和高密度的網(wǎng)絡(luò)環(huán)境中，才能達(dá)到它的最佳性能。

1.2 基于地理位置的路由協(xié)議

(1) 最優(yōu)鏈路狀態(tài)路由協(xié)議(OLSR)

OLSR[5]是根據(jù)MANET的要求，在傳統(tǒng)的LS(Link state)協(xié)議的基礎(chǔ)上優(yōu)化的。OLSR中的關(guān)鍵概念是多點(diǎn)轉(zhuǎn)播(MPRs)，MPRs是在廣播洪泛的過程中挑選的轉(zhuǎn)發(fā)廣播的節(jié)點(diǎn)。傳統(tǒng)的鏈路狀態(tài)協(xié)議每個(gè)節(jié)點(diǎn)都轉(zhuǎn)發(fā)它收到信息的第一份拷貝，同它相比，OLSR很大程度上減少了轉(zhuǎn)發(fā)的信息。在OLSR協(xié)議中，鏈路狀態(tài)信息都是由被挑選為MPRs的節(jié)點(diǎn)產(chǎn)生的，這樣減少了在網(wǎng)絡(luò)中洪泛的控制信息，實(shí)現(xiàn)了第二步優(yōu)化。第三步優(yōu)化是MPR節(jié)點(diǎn)只選擇在MPR或者M(jìn)PR選擇者之間傳遞鏈接狀態(tài)信息。因此，同傳統(tǒng)LS協(xié)議相比，在網(wǎng)絡(luò)中分布著部分鏈路狀態(tài)信息，這些信息將用于路由計(jì)算。OLSR以路由跳數(shù)提供最優(yōu)路徑。這種協(xié)議尤其適合大而密集型的網(wǎng)絡(luò)。

(2)位置輔助路由協(xié)議(LAR)

此協(xié)議利用位置信息來改進(jìn)移動(dòng)自組網(wǎng)中路由協(xié)議的性能[6]。通過全球定位系統(tǒng)來獲得位置信息。網(wǎng)絡(luò)中的路由計(jì)算僅局限于一個(gè)較小的請求區(qū)域。此協(xié)議與洪泛十分相似，唯一的不同就是只有在請求區(qū)域的節(jié)點(diǎn)才能發(fā)送路由請求。

LAR減少了路由發(fā)現(xiàn)的開銷，縮小了路由請求洪泛的范圍。其主要缺點(diǎn)是，網(wǎng)絡(luò)中的節(jié)點(diǎn)必須知道它們確切的物理位置。

(3) 基于網(wǎng)格的地域群播路由協(xié)議(GeoGRID)

GeoGRID依賴于單播協(xié)議GRID，其主要用于地域群播。它可以克服基于地址的路由協(xié)議的缺點(diǎn)，用來提供位置感知服務(wù)。該協(xié)議減少了網(wǎng)絡(luò)擁塞，能夠獲得最佳的數(shù)據(jù)到達(dá)率。地域群播[7]就是從源節(jié)點(diǎn)傳遞消息到一給定地理區(qū)域內(nèi)的所有節(jié)點(diǎn)，它基于位置而不是地址。位置信息只能通過全球定位系統(tǒng)獲得。GeoGRID將地理區(qū)域分為許多個(gè)d×d大小的正方形網(wǎng)格。在每一個(gè)網(wǎng)格中，只有一個(gè)移動(dòng)節(jié)點(diǎn)被指定為網(wǎng)格的首節(jié)點(diǎn)或網(wǎng)關(guān)，地域群播就是將消息經(jīng)由這些首節(jié)點(diǎn)從一個(gè)網(wǎng)格傳到另一個(gè)網(wǎng)格。非首節(jié)點(diǎn)不用于傳播數(shù)據(jù)包，除非它是源節(jié)點(diǎn)。地域群播路由協(xié)議可分為兩類，基于洪泛的和基于簇的。網(wǎng)關(guān)的選擇是使用一種選舉協(xié)議進(jìn)行。

此協(xié)議在因洪泛引起沖突的擁塞網(wǎng)絡(luò)中能表現(xiàn)出極佳的性能，提供高準(zhǔn)確性和低傳輸成本。

1.3 基于安全的路由協(xié)議

(1) 安全感知路由協(xié)議(SAR)

該協(xié)議是第一個(gè)具有QoS意識的路由協(xié)議。該協(xié)議以基于路由表驅(qū)動(dòng)的多路徑方式滿足網(wǎng)絡(luò)低能耗和魯棒性的要求。它的特點(diǎn)是路由決策不僅要考慮到每條路徑的能源，還要涉及端到端的延遲需求和待發(fā)送數(shù)據(jù)包的優(yōu)先級。為了在每個(gè)源節(jié)點(diǎn)和匯聚節(jié)點(diǎn)之間生成多條路徑。需要維護(hù)多個(gè)樹結(jié)構(gòu)。每個(gè)樹落在匯聚點(diǎn)有效傳輸半徑內(nèi)的節(jié)點(diǎn)為根向外生長，枝干的選擇需要滿足一定QoS要求，并要有一定的能源儲(chǔ)備。這一處理使大多數(shù)傳感器節(jié)點(diǎn)可能同時(shí)屬于多個(gè)樹?？梢愿鶕?jù)沒條路徑的能源、附加的QoS度量和包的優(yōu)先級選擇某棵樹將信息返回給匯聚節(jié)點(diǎn)。

它與只考慮路徑能量消耗的最小能量消耗度量協(xié)議相比，消耗更少；但是，它并不適合大型和拓?fù)漕l繁變化的網(wǎng)絡(luò)[8]。

(2) 安全位置輔助路由協(xié)議(SPAAR)

SPAAR的目的就是為了減少路由開銷，但是它不能在高風(fēng)險(xiǎn)的網(wǎng)絡(luò)環(huán)境中使用。該協(xié)議利用位置統(tǒng)計(jì)來提高網(wǎng)絡(luò)的性能和安全，然而只需要維護(hù)未經(jīng)授權(quán)節(jié)點(diǎn)的詳細(xì)位置信息[9]。節(jié)點(diǎn)僅接收從它們的一跳鄰居節(jié)點(diǎn)傳過來的路由信息。為了參與到路由中來，每個(gè)節(jié)點(diǎn)都要有一個(gè)公鑰/私鑰對，一種將它的身份加入到自己和受信任的證書服務(wù)器的公鑰中的證書。節(jié)點(diǎn)只允許接收從它的鄰居表中的節(jié)點(diǎn)傳來的路由消息。捏造的路由信息不能夠通過惡意節(jié)點(diǎn)插入到網(wǎng)絡(luò)中，它們也不能造成路由回路。未經(jīng)授權(quán)的節(jié)點(diǎn)必須被驅(qū)逐出路由計(jì)算和發(fā)現(xiàn)。此協(xié)議的缺點(diǎn)是，處理非對稱加密會(huì)產(chǎn)生一些開銷。

(3) 基于地理位置的隱私保護(hù)按需路由協(xié)議(PRISM)

PRISM是一種基于地理位置的反應(yīng)式路由協(xié)議。此協(xié)議是用來保護(hù)網(wǎng)絡(luò)的隱私和安全不受外部和內(nèi)部的攻擊[10]。PRISM基于AVOD協(xié)議，并保留了匿名性。

該協(xié)議實(shí)現(xiàn)了跟蹤性的行為，不傳播拓?fù)湫畔?。協(xié)議中，路由請求消息以洪泛方式在目標(biāo)地理區(qū)域中傳播，只有在指定區(qū)域中的節(jié)點(diǎn)才能轉(zhuǎn)發(fā)路由應(yīng)答消息。它使用路由請求和應(yīng)答的哈希值作為路由標(biāo)識，用群簽名進(jìn)行認(rèn)證。相比其它先驗(yàn)式的協(xié)議，該協(xié)議的路由開銷較小，通信選擇不依賴于當(dāng)前網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。它只會(huì)暴露一小部分的網(wǎng)絡(luò)拓?fù)?，但此協(xié)議限制了路由的即時(shí)可用性。

(4) 匿名的位置輔助路由協(xié)議(ALARM)

ALARM[11]是一種通過滿意的匿名性實(shí)現(xiàn)安全和隱私的先驗(yàn)式路由協(xié)議。它可以抵御外部和內(nèi)部攻擊帶來的安全威脅。此協(xié)議由群管理節(jié)點(diǎn)指定群簽名方案，將所有合理的移動(dòng)節(jié)點(diǎn)組成一個(gè)群。協(xié)議中，每個(gè)節(jié)點(diǎn)都會(huì)創(chuàng)建一個(gè)不向其他節(jié)點(diǎn)透露的私鑰和一個(gè)只透露給群管理節(jié)點(diǎn)的公鑰。然后，每個(gè)節(jié)點(diǎn)就會(huì)得到一個(gè)用來驗(yàn)證群簽名的公共密鑰。

網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)位置公告消息給所有其他節(jié)點(diǎn)，其中包含位置，時(shí)間戳，公鑰和群簽名信息。一旦收到位置公告消息，節(jié)點(diǎn)就會(huì)檢查它是否準(zhǔn)備好了，如果沒有它就會(huì)記錄下來或是丟棄掉。這樣每個(gè)節(jié)點(diǎn)就能知道其他節(jié)點(diǎn)的確切位置和網(wǎng)絡(luò)的拓?fù)?。?jié)點(diǎn)將消息用會(huì)話密鑰加密后轉(zhuǎn)發(fā)給位置信息已知的目的節(jié)點(diǎn)。會(huì)話密鑰也是用公鑰加密。ALARM協(xié)議致力于抵御跟蹤和Sybil攻擊。

2 對照表

通過相關(guān)文獻(xiàn)的參考和研究，表1對無線自組網(wǎng)中的路由協(xié)議做個(gè)比較。表中協(xié)議被分為先驗(yàn)式和反應(yīng)式，并對它們路由的基本性質(zhì)進(jìn)行了詳細(xì)說明。同時(shí)表中也列出了那些包含安全屬性的協(xié)議。最后兩欄對它們的主要優(yōu)缺點(diǎn)進(jìn)行了說明。

表1 路由協(xié)議的對比

結(jié) 語

[1] Krishna Gorantala. Routing Protocols in Mobile Ad hoc Networks[D]. Umea: Umea University, 2006.

[2] C Adjih, E Baccelli, P Jacquet. Link State Routing In Wireless Adhoc Networks[C]//Proceedings of the 2003 IEEE conference on Military communications-Volume II: 1274-1279.

[3] Guoyou He. Destination-sequenced distance vector (DSDV) protocol[D]. Helsinki: Helsinki University of Technology,2012.

[4] C E Perkins, E M Royer. Ad-hoc on-demand distance vector routing[C]// Proc. of 2nd IEEE Workshop on Mobile Computing Systems and Applications, 1999: 90-100.

[5] Jacquet P, P Muhlethaler, T Clausen, et al. Optimized link state routing protocol for ad hoc networks, 2001: 62-68.

[6] Y B Ko, N H Vaidya. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks[J]. Wireless Networks, 2000, 6(4): 307-321.

[7] Wen-Hwa Liao1, Yu-Chee Tseng, Kuo-Lun Lo,et al. GeoGRID: A Geocasting Protocol for Mobile Ad Hoc Networks Based on GRID[J]. Journal of Internet Technology, 2000,1(2):23-32.

[8] Seung Yi, Prasad Naldurg, Robin Kravets. Security - Aware Ad hoc Routing for Wireless Networks[C]// Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing: 299-302.

[9] S Carter, A Yasinsac. Secure Position Aided Ad Hoc Routing[C]// Proc. IASTED Int'l Conf. Comm. and Computer Networks (CCN '02),2002:329-334.

[10] Karim El Defrawy, Gene Tsudik. Privacy-Preserving Location-Based On-Demand Routing in MANETs[J]. IEEE Journal on Selected Areas in Communications 2011, 29(10).

[11] Karim El Defrawy, Gene Tsudik. ALARM: Anonymous Location-Aided Routing in Suspicious MANETs[J].IEEE Transactions on Mobile Computing, 2011, 10(9):1345 - 1358.

吳院(碩士研究生)，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與信息系統(tǒng)、智能協(xié)同通信技術(shù)、物聯(lián)網(wǎng)技術(shù)等。

Analysis and Research of Routing Protocols in MANET

Wu Yuan

(Key Laboratory of EDA, Research Institute of Tsinghua University in Shenzhen, Shenzhen 518057, China)

The Mobile Ad-hoc Networks (MANET) are networks with self-configuring capacity of mobile devices interconnected by wireless links. During the last few years, research in various aspects of MANET has been prominent, prompted mainly by military, disaster relief, and law enforcement scenarios. An instinctive footstep is to take up such location-based operation to MANET. In various applications, including military and law enforcement, node identities are not virtually as helpful as node locations. In suspicious MANET, nodes do not even trust each other; hence identities must be concealed. This paper attempts to contribute a study and comparison on routing protocols in mobile Ad-hoc networks.

location; MANET; routing; security

TN929.5

A

珍

2013-07-22)