肖 品， 唐子安， 陸 倩， 姜?jiǎng)倜?/p>

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

無線自組網(wǎng)（Wireless Ad hoc Network，WANet）不依賴網(wǎng)絡(luò)基礎(chǔ)設(shè)施，終端間就可以直接通信，它的自組織和自愈能力使得它容易適應(yīng)動(dòng)態(tài)和不穩(wěn)定的網(wǎng)絡(luò)環(huán)境［1］。

在WANet中，網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)，無線信道的衰落、干擾等因素造成網(wǎng)絡(luò)結(jié)構(gòu)的頻繁變化，使得路由問題比固定網(wǎng)絡(luò)要復(fù)雜很多。路由協(xié)議必須采用分布式操作，支持單向鏈路，同時(shí)應(yīng)避免環(huán)路現(xiàn)象。由于網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性、動(dòng)力資源的有限性，路由協(xié)議還應(yīng)盡量簡(jiǎn)單，支持節(jié)點(diǎn)的休眠操作以節(jié)省電源，考慮到WANet的應(yīng)用環(huán)境，路由協(xié)議還應(yīng)提供安全性保護(hù)機(jī)制。

在WANet路由協(xié)議之中，相比主動(dòng)路由協(xié)議，按需路由協(xié)議在分組投遞成功率和路由開銷方面均有著更好的表現(xiàn)。在按需路由協(xié)議中，使用源路由機(jī)制進(jìn)行分組轉(zhuǎn)發(fā)的動(dòng)態(tài)源路由（Dynamic Source Routing，DSR）協(xié)議能使源節(jié)點(diǎn)獲取更多的到達(dá)目的節(jié)點(diǎn)的路由［2］，極大地保證了數(shù)據(jù)分組在動(dòng)態(tài)變化的WANet絡(luò)中也能被成功交付。

源路由，指的是DSR路由協(xié)議中的源節(jié)點(diǎn)所發(fā)送的每個(gè)數(shù)據(jù)分組頭部都會(huì)攜帶從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)經(jīng)過的所有中間節(jié)點(diǎn)IP地址［3］。正因此，若將DSR路由協(xié)議直接應(yīng)用于資源珍貴、傳輸能耗大的WANet，頭部分組所包含完整的路由信息的路徑表達(dá)方式會(huì)對(duì)珍貴的自組網(wǎng)網(wǎng)絡(luò)資源造成極大的浪費(fèi)［4］。如何減小頭部路徑表達(dá)的帶寬消耗成為了優(yōu)化DSR協(xié)議的重要問題［5］。

1 基于動(dòng)態(tài)標(biāo)簽的動(dòng)態(tài)源路由協(xié)議

基本思想和設(shè)計(jì)思路

基于對(duì)DSR路由協(xié)議的分析［6-7］，提出一種基于動(dòng)態(tài)標(biāo)簽的源路由協(xié)議（Dynamic Label-based Source Routing，DL-DSR）用于優(yōu)化DSR路由協(xié)議。DL-DSR路由協(xié)議的基本思想是通過DL-DSR協(xié)議的鄰居發(fā)現(xiàn)策略的啟動(dòng)，在網(wǎng)絡(luò)中發(fā)現(xiàn)通信節(jié)點(diǎn)，與此同時(shí)在節(jié)點(diǎn)內(nèi)建立起鄰居表和標(biāo)簽表，通過將IP地址、鄰居表、標(biāo)簽表之間的關(guān)系進(jìn)行映射，在路徑表達(dá)字段中便可以用8 bit動(dòng)態(tài)標(biāo)簽代替原有的32 bit的IP地址，以此來減小轉(zhuǎn)發(fā)分組頭部攜帶完整路由信息的開銷［8］。

標(biāo)簽表存放鄰居節(jié)點(diǎn)IP地址以及鄰居節(jié)點(diǎn)為自身節(jié)點(diǎn)分配的標(biāo)簽號(hào)的對(duì)應(yīng)關(guān)系［9］，通過此對(duì)應(yīng)關(guān)系，可在路由請(qǐng)求階段逐步以標(biāo)簽號(hào)構(gòu)造出路徑表達(dá)字段。鄰居表存放鄰居節(jié)點(diǎn)的IP地址與自身節(jié)點(diǎn)為其分配的標(biāo)簽的對(duì)應(yīng)關(guān)系，通過此對(duì)應(yīng)關(guān)系可在轉(zhuǎn)發(fā)階段找到下一跳的IP地址。通過這種方式，便可根據(jù)路徑表達(dá)中的標(biāo)簽號(hào)而不是IP地址來進(jìn)行路徑選擇。圖1所示為DL-DSR路由協(xié)議的基本思路示意圖。

圖1 DL-DSR基本思路示意圖

2 路由表的建立

2.1 DL-DSR鄰居表的建立

DL-DSR路由協(xié)議的鄰居表和標(biāo)簽表的建立都是基于鄰居發(fā)現(xiàn)的過程，標(biāo)簽表的建立是基于鄰居表的建立。當(dāng)DL-DSR路由協(xié)議的鄰居發(fā)現(xiàn)過程啟動(dòng)后，節(jié)點(diǎn)會(huì)廣播hello消息分組將自身節(jié)點(diǎn)地址和鄰居發(fā)現(xiàn)開始的時(shí)間告知其鄰居節(jié)點(diǎn)。

hello數(shù)據(jù)分組包含了IP地址、啟動(dòng)時(shí)間兩條信息。IP地址：發(fā)送節(jié)點(diǎn)自身的IP地址；啟動(dòng)時(shí)間：開始發(fā)送hello消息分組的時(shí)間，即鄰居發(fā)現(xiàn)過程啟動(dòng)的時(shí)間。

當(dāng)節(jié)點(diǎn)收到hello消息分組后，首先取出hello消息分組中的IP地址，在鄰居表中查找是否已經(jīng)存在此IP地址，若存在，則將此IP地址對(duì)應(yīng)的時(shí)間戳比較并更新；否則，將IP地址和時(shí)間戳一同插入一處空閑的存儲(chǔ)空間。若鄰居信息丟失或過期，則應(yīng)該刪除相應(yīng)的存儲(chǔ)空間信息。DL-DSR路由協(xié)議的鄰居表如圖2所示。

圖2 鄰居表結(jié)構(gòu)

鄰居信息包含標(biāo)簽號(hào)、IP地址和時(shí)間戳3個(gè)條目。標(biāo)簽：節(jié)點(diǎn)為其鄰居節(jié)點(diǎn)分配的標(biāo)簽號(hào)；IP地址：鄰居節(jié)點(diǎn)地址；時(shí)間戳：hello消息分組中攜帶的時(shí)間或鄰居表更新時(shí)間。

2.2 DL-DSR標(biāo)簽表的建立

DL-DSR路由協(xié)議標(biāo)簽表是建立在鄰居表的基礎(chǔ)上。在節(jié)點(diǎn)收到hello消息分組并成功將分組中的鄰居信息存儲(chǔ)到鄰居表后，節(jié)點(diǎn)會(huì)向hello消息發(fā)送方回復(fù)hello_reply消息分組，告知發(fā)送方本節(jié)點(diǎn)的IP地址和本節(jié)點(diǎn)為發(fā)送方所分配的標(biāo)簽號(hào)。

hello_reply數(shù)據(jù)分組包含IP地址、標(biāo)簽和標(biāo)識(shí)符3條信息。IP地址：hello_reply分組發(fā)送節(jié)點(diǎn)自身的IP地址；標(biāo)簽：發(fā)送節(jié)點(diǎn)為hello消息分組來源節(jié)點(diǎn)分配的標(biāo)簽號(hào)；標(biāo)識(shí)符：若是收到hello消息分組后發(fā)送的標(biāo)識(shí)符為0，若是鄰居表更新后發(fā)送的則為1。根據(jù)收到的hello_reply消息分組，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)將收到的鄰居IP地址以及鄰居節(jié)點(diǎn)為自己分配的標(biāo)簽號(hào)存入自身的標(biāo)簽表之中，依此完成標(biāo)簽表的建立。標(biāo)簽表結(jié)構(gòu)如圖3所示。

圖3 標(biāo)簽表結(jié)構(gòu)

標(biāo)簽表信息包含IP地址和標(biāo)簽兩個(gè)條目。IP地址：鄰居節(jié)點(diǎn)的IP地址；標(biāo)簽：鄰居節(jié)點(diǎn)為自己分配的標(biāo)簽號(hào)。

2.3 路由表建立示意

圖4描述了以S、A、B、C、D為節(jié)點(diǎn)的網(wǎng)絡(luò)標(biāo)簽表建立階段，同一顏色表示數(shù)據(jù)的同一映射關(guān)系。圖4中節(jié)點(diǎn)A在成功處理S節(jié)點(diǎn)發(fā)來的hello消息后回復(fù)S節(jié)點(diǎn)hello_reply消息，消息中包含節(jié)點(diǎn)A自己的ip地址“ip_A”、自己為節(jié)點(diǎn)S分配的標(biāo)簽號(hào)“1”以及標(biāo)識(shí)符“0”，當(dāng)節(jié)點(diǎn)S收到此消息后，將“ip_A”和“1”寫入自己的標(biāo)簽表內(nèi)。

圖4 標(biāo)簽表建立示意圖

3 路由請(qǐng)求和應(yīng)答過程的優(yōu)化方案

當(dāng)源節(jié)點(diǎn)有數(shù)據(jù)要發(fā)送時(shí)，首先會(huì)查找節(jié)點(diǎn)本地的路由緩存（cache）中是否存在能到達(dá)目的節(jié)點(diǎn)的路由。如果存在，且這條路由是有效的，就根據(jù)這條路由將數(shù)據(jù)分組發(fā)送出去。若不存在，源節(jié)點(diǎn)則產(chǎn)生一個(gè)路由請(qǐng)求（Route Requset，RREQ）分組［4］，啟動(dòng)路由請(qǐng)求階段。RREQ請(qǐng)求分組格式如圖5所示。

圖5 RREQ分組格式

當(dāng)節(jié)點(diǎn)收到一個(gè)RREQ分組時(shí)，首先判斷自己是否已經(jīng)接收過這個(gè)RREQ分組，若是已經(jīng)收到過這個(gè)RREQ分組，就丟棄。否則判斷自己是否是目的節(jié)點(diǎn)，若是，則向源節(jié)點(diǎn)回復(fù)RREP（Route Reply）分組啟動(dòng)路由應(yīng)答（分組格式如圖6所示），若不是，繼續(xù)判斷路由緩存中是否存在能到達(dá)目的節(jié)點(diǎn)的路由信息，若存在，就回復(fù)RREP分組啟動(dòng)路由應(yīng)答，若不存在，就將本節(jié)點(diǎn)標(biāo)簽號(hào)加到路徑中，并向鄰居轉(zhuǎn)發(fā)更新后的RREQ分組。

圖6 RREP分組格式

DL-DSR路由協(xié)議規(guī)定在向前轉(zhuǎn)發(fā)一個(gè)RREQ分組前，先會(huì)根據(jù)上一跳節(jié)點(diǎn)的IP地址從當(dāng)前的標(biāo)簽表中找到對(duì)應(yīng)的標(biāo)簽號(hào)，填充到RREQ分組頭部的路徑表達(dá)中，再向周圍鄰居節(jié)點(diǎn)廣播出去。依次方式，會(huì)逐步建立起一條完整的路徑表達(dá)［10-11］。路由請(qǐng)求應(yīng)答流程如圖7所示。

圖7 路由請(qǐng)求應(yīng)答流程圖

此外，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)還維護(hù)著一個(gè)路由緩存，其中存有該節(jié)點(diǎn)在以前路由發(fā)現(xiàn)中得到的路由。當(dāng)源節(jié)點(diǎn)收到RREP分組時(shí)，便將分組中攜帶的路徑存入路由緩存中，依此建立起路由緩存。路由緩存既能減小路由發(fā)現(xiàn)的延遲，又能很好地應(yīng)對(duì)路由失效問題。DL-DSR協(xié)議中路由緩存的索引是目標(biāo)地址，當(dāng)路由緩存中存在不止一條到達(dá)同一個(gè)目的地址的路徑時(shí)，緩存信息的讀取是找到最短的一條路徑，即跳數(shù)最少的一條路徑。如果出現(xiàn)路由失效現(xiàn)象，源節(jié)點(diǎn)便利用路由緩存中的備選路由代替失效路由發(fā)送數(shù)據(jù)分組。

如圖8所示，節(jié)點(diǎn)S為源節(jié)點(diǎn)，節(jié)點(diǎn)D為目的節(jié)點(diǎn)，當(dāng)S節(jié)點(diǎn)檢查自己路由緩存發(fā)現(xiàn)無到達(dá)目節(jié)點(diǎn)的路徑，便產(chǎn)生了一個(gè)RREQ分組，啟動(dòng)路由請(qǐng)求發(fā)給自己的鄰居節(jié)點(diǎn)A、B。以A節(jié)點(diǎn)為例，當(dāng)A收到S發(fā)出的RREQ，A節(jié)點(diǎn)會(huì)檢查自己的路由緩存也無目標(biāo)節(jié)點(diǎn)的路徑，于是查找自己標(biāo)簽表，找到上一跳的ip地址，也就是S節(jié)點(diǎn)的ip地址“IP_S”對(duì)應(yīng)的標(biāo)簽號(hào)“1”，將“1”寫入RREQ路徑表達(dá)中，并向鄰居節(jié)點(diǎn)S、C轉(zhuǎn)發(fā)更新后的RREQ請(qǐng)求。當(dāng)S收到此RREQ后根據(jù)請(qǐng)求序列號(hào)發(fā)現(xiàn)自己收到過，于是丟棄；當(dāng)C點(diǎn)收到后按協(xié)議規(guī)則繼續(xù)處理。最終到達(dá)目標(biāo)節(jié)點(diǎn)D，D節(jié)點(diǎn)將完整的路徑“1→2→2”填入生成的RREP消息分組中，以倒序路徑回傳給S節(jié)點(diǎn)。S節(jié)點(diǎn)收到此RREP消息后，將其中的路徑表達(dá)取出存入自己的路由緩存中，路由請(qǐng)求結(jié)束，進(jìn)行以S為源節(jié)點(diǎn)D為目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)便可以使用這一路徑。路由請(qǐng)求和應(yīng)答過程的示意如圖8所示。

圖8 路由請(qǐng)求應(yīng)答過程示意圖

4 仿真與分析

4.1 仿真場(chǎng)景

將DL-DSR路由協(xié)議方案進(jìn)行仿真分析，使用EXata網(wǎng)絡(luò)仿真軟件。仿真之前，需要先在EXata上面搭建一個(gè)仿真的WANet場(chǎng)景［12］。仿真主要參數(shù)：區(qū)域大小為6 km×6 km；仿真時(shí)長(zhǎng)為1 h；節(jié)點(diǎn)移動(dòng)模型和速度分別為隨機(jī)路點(diǎn)（RandomWaypoint）和0～30m/s；能量消耗模型為通用型（Generic）；應(yīng)用層業(yè)務(wù)流為恒定比特率（CBR）；鄰居發(fā)現(xiàn)周期800 ms；有效數(shù)據(jù)長(zhǎng)度為64～512 Byte；路徑跳數(shù)為4～32跳［13］。

4.2 仿真結(jié)果分析

4.2.1 網(wǎng)絡(luò)負(fù)載與路徑中節(jié)點(diǎn)跳數(shù)

圖9（a）、（b）分別為有效數(shù)據(jù)長(zhǎng)度在64和512 Byte的節(jié)點(diǎn)網(wǎng)絡(luò)負(fù)載（單位Kb/s）和路徑中節(jié)點(diǎn)跳數(shù)的關(guān)系。

圖9 網(wǎng)絡(luò)負(fù)載和路徑中節(jié)點(diǎn)跳數(shù)的關(guān)系

由仿真結(jié)果可見，在有效數(shù)據(jù)長(zhǎng)度相同、跳數(shù)相同的情況下，DL-DSR協(xié)議的網(wǎng)絡(luò)負(fù)載均小于DSR協(xié)議的網(wǎng)絡(luò)負(fù)載，并隨著中節(jié)點(diǎn)跳數(shù)增大，兩者的傳輸負(fù)載差值越來越大，DL-DSR協(xié)議的網(wǎng)絡(luò)負(fù)載增長(zhǎng)緩慢，明顯低于DSR協(xié)議。

4.2.2 端到端平均時(shí)延與路徑中節(jié)點(diǎn)跳數(shù)

圖10（a）、（b）分別為有效數(shù)據(jù)長(zhǎng)度在64和512 Byte的節(jié)點(diǎn)平均端到端時(shí)延與路徑中節(jié)點(diǎn)跳數(shù)之間的關(guān)系。

圖10 平均時(shí)延與路徑中節(jié)點(diǎn)跳數(shù)的關(guān)系

由仿真結(jié)果可見，在有效數(shù)據(jù)長(zhǎng)度相同的情況下，DL-DSR協(xié)議和DSR協(xié)議端到端時(shí)延隨著路徑中節(jié)點(diǎn)跳數(shù)的增加而增大；當(dāng)路徑中節(jié)點(diǎn)跳數(shù)相同時(shí)，DLDSR協(xié)議節(jié)點(diǎn)間平均端到端時(shí)延都比DSR協(xié)議小。說明DL-DSR協(xié)議減小路徑表達(dá)占用的帶寬的方式，在一定程度上的確減小數(shù)據(jù)傳輸?shù)亩说蕉藭r(shí)延。

4.2.3 節(jié)點(diǎn)平均能耗與路徑中節(jié)點(diǎn)跳數(shù)

圖11（a）、（b）分別為有效數(shù)據(jù)長(zhǎng)度在64和512 Byte的節(jié)點(diǎn)平均能耗與路徑中節(jié)點(diǎn)跳數(shù)的關(guān)系。

圖11 平均能耗與路徑中節(jié)點(diǎn)跳數(shù)的關(guān)系

由仿真結(jié)果可見，在有效數(shù)據(jù)長(zhǎng)度一定的情況下，節(jié)點(diǎn)平均能耗會(huì)隨著路徑中節(jié)點(diǎn)跳數(shù)的增大而增大，DL-DSR協(xié)議節(jié)點(diǎn)平均能耗是明顯低于DSR協(xié)議的。對(duì)于能耗增長(zhǎng)速度，特別是當(dāng)路徑中節(jié)點(diǎn)跳數(shù)增大時(shí)，DL-DSR協(xié)議節(jié)點(diǎn)平均能耗增長(zhǎng)速度比DSR協(xié)議的節(jié)點(diǎn)平均能耗增長(zhǎng)速度慢。

5 結(jié)語

通過對(duì)WANet中的DSR路由協(xié)議進(jìn)行分析研究，發(fā)現(xiàn)其數(shù)據(jù)分組頭部所攜帶的完整路由IP地址列表會(huì)對(duì)網(wǎng)絡(luò)性能帶來影響，提出一種基于動(dòng)態(tài)標(biāo)簽源路由（DL-DSR）協(xié)議，DL-DSR協(xié)議通過采用動(dòng)態(tài)標(biāo)簽代替節(jié)點(diǎn)IP地址來表示數(shù)據(jù)分組頭部的路由路徑的方式來解決此問題。

通過對(duì)仿真結(jié)果的分析：在跳數(shù)為32、有效數(shù)據(jù)長(zhǎng)度為512 Byte的仿真場(chǎng)景中，DL-DSR路由協(xié)議相比于DSR路由協(xié)議，網(wǎng)絡(luò)負(fù)載降低約15%，平均時(shí)延降低約10%，平均能耗降低約10%；在有效數(shù)據(jù)長(zhǎng)度為64 Byte的仿真場(chǎng)景中，DL-DSR路由協(xié)議相比DSR路由協(xié)議，網(wǎng)絡(luò)負(fù)載降低約40%，平均時(shí)延降低約15%，平均能耗降低約18%。

綜上，DL-DSR協(xié)議在網(wǎng)絡(luò)負(fù)載、端到端時(shí)延、頭部開銷和節(jié)點(diǎn)能耗方面都具有一定優(yōu)勢(shì)，特別是當(dāng)源節(jié)點(diǎn)距目的節(jié)點(diǎn)較遠(yuǎn)需要經(jīng)過較多跳數(shù)才能將數(shù)據(jù)分組交付時(shí)，DL-DSR協(xié)議相較于DSR協(xié)議，有著更低的網(wǎng)絡(luò)負(fù)載、更低的端到端時(shí)延和更低的節(jié)點(diǎn)能耗，表現(xiàn)出更好的網(wǎng)絡(luò)性能。