移動自組網中路由協議的分析與研究

吳 院

(深圳清華大學研究院 EDA重點實驗室，深圳 518057)

?

移動自組網中路由協議的分析與研究

吳 院

(深圳清華大學研究院 EDA重點實驗室，深圳 518057)

移動自組網是一種由具有自配置功能的移動設備通過無線連接方式組成的網絡。近幾年來，對無線自組網各方面的研究十分突出，尤其是在災難救援和執法等領域。一個自然而然的想法就是，將基于位置的操作引進到無線自組網中。在各種應用中，節點的身份認證事實上往往不如節點的位置有用。在可疑的無線自組網中，節點之間甚至不能信任彼此，因此它們的身份必須隱藏。本文將對移動自組網中的路由協議進行研究和對比。

位置；移動自組網；路由；安全

引 言

移動自組網(MANET)是由移動無線設備組成的自配置動態網絡。網絡中的節點能夠獨立地向各個方向移動。節點之間的拓撲結構和鏈路經常發生變化。移動自組網允許用戶交換信息而不用考慮它們變動的基礎設施。移動自組網在災難救援、商業和個人局域網等領域有大量的應用。

路由就是指數據包從一個網絡傳送到另一個網絡或從網絡中的一個主機節點傳送到另一個主機節點的過程。路由功能主要由專門配置的路由器節點承擔，常常與橋接技術相混淆。基于網絡結構，路由策略可分為平面路由、層次路由和基于地理位置的路由(地理位置輔助路由)[1]。先驗式(表驅動路由)和反應式(按需路由)協議屬于平面路由，在表驅動路由下每個節點都擁有網絡中所有其他節點的路由信息，并且當網絡拓撲結構發生變化時更新路由信息。每個節點將路由信息存儲在路由表中。反應式協議只有當節點之間需要路由請求和應答時才會建立路由。混合協議就是為了融合先驗式和反應式協議的優缺點。

本文將從基本的、基于地理位置的和基于安全的路由協議的分類出發，對移動自組網的路由協議進行一個粗略的研究，主要側重于各協議優缺點的分析。

1 移動自組網路由協議的研究

1.1 基本的路由協議

(1) 鏈路狀態路由協議(LSR)

LSR[2]是一個基本的先驗式路由協議，根據當前條件發現路由，由Dijkstra提出的最短路徑優先算法發展而來，其中每個節點都擁有整個網絡的拓撲結構圖。網絡中的所有節點定期更新網絡拓撲圖，建立一個直連鏈路狀態數據包，并廣播給鄰居節點。網絡中的每個節點廣播從它的鄰居節點接收到的鏈路狀態數據包，直到每個節點都有相同的路由信息。節點記錄下從其他節點收到的鏈路狀態信息，由此建立拓撲結構圖，從而找到其他節點的最佳路徑。

LSR收斂速度較快，并且能讓節點擁有整個網絡的拓撲結構圖。但是它對存儲、CPU處理速度和網絡帶寬的需求較高。

(2) 目標序列距離矢量路由協議(DSDV)

DSDV是一種先驗式路由協議，它通過在路由表項里增加序列號，解決了距離矢量路由中的回路問題。與鏈路狀態協議不同的是，它不能獲得整個網絡的拓撲圖，然而它能容忍網絡內部或網絡之間拓撲結構的快速變化。每個節點維護著到所有已知的目標節點的路由信息，并定期更新。在路由選擇時，通常選取擁有最高序列號的路徑，在具有相同序列號的情況下，選擇具有最高度量值的路徑。DSDV[3]開銷很大，即使網絡拓撲沒有發生變化，也要存儲那些不再使用的路徑信息。

DSDV對拓撲結構的改變反應迅速，并能確保沒有路由回路。它的主要缺點是，大部分的路由信息從不使用，從而開銷很大。

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

AVOD是一種反應式路由協議，它僅在需要時才去發現到某個特定目標的路由，并維護這一路由信息。AVOD[4]優于DSR，它能減少在網絡中傳送的數據包報頭的大小，并且擁有路由表。AVOD效仿路由發現和路由維護階段通過路由請求和路由回復消息。源節點大量發出路由請求消息，網絡中的其他節點轉播這個請求，從而形成反過來指向這一源節點的路徑，當預期的目標節點收到此消息時，它就會回復一條路由回復消息給源節點。

AVOD協議減少了控制信息的開銷，并且對網絡拓撲的改變反應迅速。其主要缺點是，只有在低擁塞和高密度的網絡環境中，才能達到它的最佳性能。

1.2 基于地理位置的路由協議

(1) 最優鏈路狀態路由協議(OLSR)

OLSR[5]是根據MANET的要求，在傳統的LS(Link state)協議的基礎上優化的。OLSR中的關鍵概念是多點轉播(MPRs)，MPRs是在廣播洪泛的過程中挑選的轉發廣播的節點。傳統的鏈路狀態協議每個節點都轉發它收到信息的第一份拷貝，同它相比，OLSR很大程度上減少了轉發的信息。在OLSR協議中，鏈路狀態信息都是由被挑選為MPRs的節點產生的，這樣減少了在網絡中洪泛的控制信息，實現了第二步優化。第三步優化是MPR節點只選擇在MPR或者MPR選擇者之間傳遞鏈接狀態信息。因此，同傳統LS協議相比，在網絡中分布著部分鏈路狀態信息，這些信息將用于路由計算。OLSR以路由跳數提供最優路徑。這種協議尤其適合大而密集型的網絡。

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

此協議利用位置信息來改進移動自組網中路由協議的性能[6]。通過全球定位系統來獲得位置信息。網絡中的路由計算僅局限于一個較小的請求區域。此協議與洪泛十分相似，唯一的不同就是只有在請求區域的節點才能發送路由請求。

LAR減少了路由發現的開銷，縮小了路由請求洪泛的范圍。其主要缺點是，網絡中的節點必須知道它們確切的物理位置。

(3) 基于網格的地域群播路由協議(GeoGRID)

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

此協議在因洪泛引起沖突的擁塞網絡中能表現出極佳的性能，提供高準確性和低傳輸成本。

1.3 基于安全的路由協議

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

該協議是第一個具有QoS意識的路由協議。該協議以基于路由表驅動的多路徑方式滿足網絡低能耗和魯棒性的要求。它的特點是路由決策不僅要考慮到每條路徑的能源，還要涉及端到端的延遲需求和待發送數據包的優先級。為了在每個源節點和匯聚節點之間生成多條路徑。需要維護多個樹結構。每個樹落在匯聚點有效傳輸半徑內的節點為根向外生長，枝干的選擇需要滿足一定QoS要求，并要有一定的能源儲備。這一處理使大多數傳感器節點可能同時屬于多個樹。可以根據沒條路徑的能源、附加的QoS度量和包的優先級選擇某棵樹將信息返回給匯聚節點。

它與只考慮路徑能量消耗的最小能量消耗度量協議相比，消耗更少；但是，它并不適合大型和拓撲頻繁變化的網絡[8]。

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

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

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

PRISM是一種基于地理位置的反應式路由協議。此協議是用來保護網絡的隱私和安全不受外部和內部的攻擊[10]。PRISM基于AVOD協議，并保留了匿名性。

該協議實現了跟蹤性的行為，不傳播拓撲信息。協議中，路由請求消息以洪泛方式在目標地理區域中傳播，只有在指定區域中的節點才能轉發路由應答消息。它使用路由請求和應答的哈希值作為路由標識，用群簽名進行認證。相比其它先驗式的協議，該協議的路由開銷較小，通信選擇不依賴于當前網絡的拓撲結構。它只會暴露一小部分的網絡拓撲，但此協議限制了路由的即時可用性。

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

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

網絡中每個節點轉發位置公告消息給所有其他節點，其中包含位置，時間戳，公鑰和群簽名信息。一旦收到位置公告消息，節點就會檢查它是否準備好了，如果沒有它就會記錄下來或是丟棄掉。這樣每個節點就能知道其他節點的確切位置和網絡的拓撲。節點將消息用會話密鑰加密后轉發給位置信息已知的目的節點。會話密鑰也是用公鑰加密。ALARM協議致力于抵御跟蹤和Sybil攻擊。

2 對照表

通過相關文獻的參考和研究，表1對無線自組網中的路由協議做個比較。表中協議被分為先驗式和反應式，并對它們路由的基本性質進行了詳細說明。同時表中也列出了那些包含安全屬性的協議。最后兩欄對它們的主要優缺點進行了說明。

表1 路由協議的對比

結 語

[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.

吳院(碩士研究生)，研究方向為計算機網絡與信息系統、智能協同通信技術、物聯網技術等。

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)