1、LSR 協(xié)議

LSR 為基于鏈路狀態(tài)的路由算法。如何判斷鏈路狀態(tài)呢？在無線通信的環(huán)境下，只需要節(jié)點(diǎn)能夠收到另一節(jié)點(diǎn)的包，就說明鏈路有效。另一方面，為了建立端到端的路徑，路由算法需要發(fā)現(xiàn)并檢查一跳由多個(gè)單跳鏈接組成的多條鏈路的可用性，這就需要不斷的洪泛廣播(flooding)來進(jìn)行。這種洪泛的方式是非常浪費(fèi)的。

為了在網(wǎng)絡(luò)中同步節(jié)點(diǎn)狀態(tài)，需要各個(gè)節(jié)點(diǎn)進(jìn)行洪泛廣播，產(chǎn)生大量冗余的通信，在能源受限的移動(dòng)網(wǎng)絡(luò)中是非常不經(jīng)濟(jì)的。OLSR 通過有選擇的洪泛轉(zhuǎn)發(fā)(MPR: Multi-Point Relay)來解決這個(gè)問題。

2、OLSR 協(xié)議

OLSR（Optimized Link State Routing: RFC 3626, October 2003）是一種基于連接狀態(tài)的表驅(qū)動(dòng)無線路由協(xié)議，它在 Ad Hoc 路由協(xié)議中的位置如下圖所示。

OLSR 包使用 IP 地址作為其在網(wǎng)絡(luò)中的唯一標(biāo)識，兼容 IPv4 和 IPv6 兩種格式，下面以 IPv4 為例說明其包格式：

OLSR 包由以下幾部分組成：

• Packet length 包的字節(jié)長度
• Packet sequence number 包的序列號
• Message type 消息類型
  • 1 -> Hello
  • 2 -> topology control(TC)
  • 3 -> multiple interface declaration(MID)
  • 4 -> host and network association(HNA)
• Vtime 節(jié)點(diǎn)接收消息后消息的有效時(shí)間
• Message size 消息的字節(jié)長度
• Originator address 產(chǎn)生消息的節(jié)點(diǎn)的地址
• TTL 最大跳數(shù)
• Hop count 當(dāng)前跳數(shù)
• Message sequence number 消息的序列號
• Data 真正的消息

3、OLSR 協(xié)議的操作

3.1 鄰節(jié)點(diǎn)探測

OLSR 的節(jié)點(diǎn)中存儲了大量的數(shù)據(jù)表，主要有以下三種：

• MPR selector set 這個(gè)表記錄了本地選為 MPR 的節(jié)點(diǎn)
• neighbor set 這個(gè)表記錄了所有的一跳鄰節(jié)點(diǎn)
• Two-hop neighbor set 這個(gè)表記錄了可通過一跳鄰節(jié)點(diǎn)接觸的節(jié)點(diǎn)，可能包括上述一跳鄰節(jié)點(diǎn)

由于發(fā)送消息至一跳鄰節(jié)點(diǎn)、兩跳鄰節(jié)點(diǎn)和定義 MPR 都需要用到 HELLO 消息，所以首先介紹一下 HELLO 消息。下圖是 HELLO 消息的格式，它位于 OLSR 包的 data 域，傳播 HELLO 消息的 OLSR 包的 Message Type 和 TTL 域都為1。

HELLO 消息由以下幾個(gè)部分組成：

• Reserved 設(shè)為0000000000000
• HTime 該接口 HELLO 消息的發(fā)送間隔
• Willingness 一個(gè)節(jié)點(diǎn)為其他節(jié)點(diǎn)傳播消息的意愿，分為 WILL_NEVER，WILL_ALWAYS 和 WILL_DEFAULT
• Link code
• Neighbor type 表明一個(gè)連接時(shí) symmetric，asymmetric 還是 failed link
• Link type 表明連接的節(jié)點(diǎn)是一個(gè)一跳鄰節(jié)點(diǎn)，MPR 還是不可用節(jié)點(diǎn)
• Link message size 從當(dāng)前 Link Code 到下一個(gè) Link Code 的長度
• Neighbor interface address 一個(gè)鄰節(jié)點(diǎn)的接口地址

OLSR 通過周期性地廣播 HELLO 消息來進(jìn)行鄰節(jié)點(diǎn)探測，建立鄰居表，一般檢測兩個(gè)節(jié)點(diǎn)之間鏈路狀態(tài)的流程如下：

以 A 和 B 兩個(gè)節(jié)點(diǎn)舉例，想要檢測它們之間鏈路的狀態(tài)，需要進(jìn)行以下幾步：

1. A 向 B 發(fā)送空的 HELLO 消息。
2. B 接收到消息后，由于沒有在消息中找到 B 自己的地址，所以將 A 設(shè)為非對稱鄰節(jié)點(diǎn)。2秒后，B 向 A 發(fā)送攜帶 A 地址的 HELLO 消息。
3. A 接收到消息后，在消息中找到了自己的地址，所以將 B 定義為對稱鏈路，接著再向 B 發(fā)送帶有 B 地址的 HELLO 消息。
4. B 收到最新消息后，將 A 視為對稱鄰節(jié)點(diǎn)。

基于這個(gè)機(jī)制，OLSR 中的節(jié)點(diǎn)可以進(jìn)行鄰節(jié)點(diǎn)的探測，如果與某個(gè)鄰節(jié)點(diǎn)的連接狀態(tài)變?yōu)殡p向?qū)ΨQ連接，則記錄在 neighbor set 中，并開放接口連接鄰節(jié)點(diǎn)；如果連接狀態(tài)建立失敗，則刪除記錄。

通過 HELLO 消息廣播過程，可以讓網(wǎng)絡(luò)中所有節(jié)點(diǎn)都能知曉距離自己兩跳及以內(nèi)的鄰居的信息。

3.2 MPR 的選擇

基于上述過程建立的鄰居信息表，節(jié)點(diǎn)可以選擇出鄰居 MPR 節(jié)點(diǎn)集合。一個(gè)節(jié)點(diǎn)選定的 MPR 是負(fù)責(zé)轉(zhuǎn)發(fā)此節(jié)點(diǎn)的廣播消息的節(jié)點(diǎn)，通過控制 MPR 集合的大小可以減少洪泛的開銷。

如下圖所示情況為例，左側(cè)為經(jīng)典的洪泛技術(shù)，每個(gè)中心節(jié)點(diǎn)需要傳播信息到其所有鄰節(jié)點(diǎn)；右側(cè)為引入 MPR 技術(shù)的 OLSR 協(xié)議，每個(gè)節(jié)點(diǎn)只需將信息傳送到其 MPR 節(jié)點(diǎn)集合，并由它們廣播消息。

MPR 的選擇主要分為兩步：

1. 首先選擇能夠覆蓋孤立兩跳鄰節(jié)點(diǎn)的一跳鄰節(jié)點(diǎn)。這里的孤立兩跳鄰節(jié)點(diǎn)是指僅通過一個(gè)鄰節(jié)點(diǎn)同目標(biāo)節(jié)點(diǎn)相連的兩跳鄰節(jié)點(diǎn)。
2. 在余下的一跳鄰節(jié)點(diǎn)中，按照覆蓋二跳鄰節(jié)點(diǎn)的數(shù)量從高到低依次選擇，直到覆蓋所有的兩跳鄰節(jié)點(diǎn)。

為了方便理解，以下圖中的情況為例，找出“1”節(jié)點(diǎn)的最小 MPR 集合。

首先定義其所有的兩跳鄰節(jié)點(diǎn)（不包括一跳鄰節(jié)點(diǎn)）。

然后找到其孤立兩跳鄰節(jié)點(diǎn) 2 和 24，然后將連接它們的一跳鄰節(jié)點(diǎn) 4 和 22 加入 MPR 集合。

最后按照覆蓋二跳鄰節(jié)點(diǎn)的數(shù)量從高到低依次選擇，其中15覆蓋4個(gè)，18、5、10覆蓋三個(gè)，因?yàn)檫x擇5和10都可以滿足覆蓋所有兩跳鄰節(jié)點(diǎn)，所以選擇它們兩個(gè)中任意一個(gè)即可。

在本地節(jié)點(diǎn)被選作 MPR 后，它會(huì)向其鄰節(jié)點(diǎn)發(fā)送初始化為 MPR_NEIGH 的 HELLO 消息，鄰節(jié)點(diǎn)收到消息后更新其 MPR selector set，此表表明節(jié)點(diǎn)應(yīng)該轉(zhuǎn)發(fā)來自哪些節(jié)點(diǎn)廣播消息。

3.3 拓?fù)涔芾?/h3>

鄰節(jié)點(diǎn)探測使用了 HELLO 消息，拓?fù)涔芾韯t是用另一種格式的消息：Topology Control 消息。MPR 會(huì)定期發(fā)送 TC 消息，其中包含了選擇這個(gè)節(jié)點(diǎn)作為 MPR 的節(jié)點(diǎn)的集合。

• ANSN 與接收消息鄰節(jié)點(diǎn)關(guān)聯(lián)的序列號，代表信息的新鮮度
• Reserved 這個(gè)字段固定設(shè)為0000000000000000
• Advertised neighbor main address 是選擇這個(gè)節(jié)點(diǎn)作為 MPR 的節(jié)點(diǎn)的集合，也稱為 MPR Selector

基于 TC 消息的交換，各個(gè)節(jié)點(diǎn)可以維護(hù)一個(gè) Topology Table（拓?fù)浔恚?，拓?fù)浔淼慕Y(jié)構(gòu)如下：

Destination address	Destination’s MPR	MPR SelectorSequence Number	Holding Time

• Destination address 目標(biāo)地址
• Destination’s MPR 目標(biāo)地址的 MPR 節(jié)點(diǎn)
• MPR SelectorSequence Number 序列號
• Holding Time 該條目的保持時(shí)間

上面提到 TC 消息中包含的是發(fā)送節(jié)點(diǎn)的 MPR Selector 列表。那么當(dāng)另一節(jié)點(diǎn)收到 TC 消息時(shí)，將 TC 條目中的 MPR Selector 作為目標(biāo)地址，則發(fā)送節(jié)點(diǎn)即為其 MPR 節(jié)點(diǎn)，然后填入 TC 消息中的 Sequence Number，已經(jīng)預(yù)定義的 Holding Time。

下面舉一個(gè)例子說明拓?fù)涔芾淼倪^程，這個(gè)例子中 A、B、C 三個(gè)節(jié)點(diǎn)均將 M 作為自己的 MPR 節(jié)點(diǎn)，那么 M 會(huì)建立如下的 MPR Selector 列表：

TC Originator	MPR Selector	MPR Selector Sequence
M	A	1
M	B	1
M	C	1

作為 MPR，M 會(huì)將其 MPR Selector 列表通過 TC 消息廣播出去。當(dāng) Y 收到 M 發(fā)出的 TC 消息時(shí)，將 TC 消息中包含的 MPR Selector 信息轉(zhuǎn)化成拓?fù)浔?(Holding Time 省略)：

Destination address	Destination’s MPR	MPR SelectorSequence Number
A	M	1
B	M	1
C	M	1
…	…	…

網(wǎng)絡(luò)中周期性的通過 TC 消息保持拓?fù)浔砀?，通過拓?fù)浔砜梢杂?jì)算出全局路由表。

3.4 路由表計(jì)算

基于拓?fù)浔砗袜徆?jié)點(diǎn)信息，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都維護(hù)一張路由表（Routing Table），路由表格式如下圖所示：

• R_dest_addr 目的地址
• R_next_addr 下一跳地址
• R_dist 本地節(jié)點(diǎn)到目的地址估計(jì)的距離
• R_iface_id 是到達(dá)目的地址的本地接口編號

每次更新拓?fù)湫畔ⅲ酚杀矶夹枰匦掠?jì)算，計(jì)算步驟如下：

1. 刪除之前的所有記錄
2. 添加所有一跳對稱鄰節(jié)點(diǎn)，R_dist 通常設(shè)為1
3. 添加超過1跳（1+h）的目的節(jié)點(diǎn)。如果拓?fù)浔碇械?Destination address 在路由表的 R_dest_addr 中沒有對應(yīng)的話，就新添加一條路由：
   a. R_dest_addr = Destination address
   b. R_next_addr 設(shè)為 R_dest_addr 與拓?fù)浔碇?Destination’s MPR 相等的路由表記錄的 R_next_addr
   c. R_dist = h + 1
4. 計(jì)算完路由表后，如果想節(jié)省空間，可以刪除拓?fù)浔碇袥]有用到的字段。

OLSR 協(xié)議相對 AODV 復(fù)雜，RFC 頁數(shù)就是其2倍，以上內(nèi)容是我根據(jù)相關(guān)材料進(jìn)行的總結(jié)。

此外，我們組研讀了 OLSR 協(xié)議的 RFC，整理的完整版 PDF 在這里。

參考

• Ad Hoc Networks: Routing, QoS and Optimization
• RFC 3626 Optimized Link State Routing
• Optimized Link State Routing Protocol for Ad Hoc Networks
• OLSR: Optimized Link State Routing
• OLSR routing protocol in NS2
• OLSR 路由算法原理

到此這篇關(guān)于自組織網(wǎng)絡(luò)Ad Hoc之AODV協(xié)議詳解的文章就介紹到這了,更多相關(guān)AODV協(xié)議內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持腳本之家！

最新評論