6LoWPAN多跳網(wǎng)狀路由協(xié)議設(shè)計(jì)與仿真

程宏斌

(常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500)

0 引言

將IPv6與無(wú)線傳感器網(wǎng)絡(luò)結(jié)合是當(dāng)前的一個(gè)熱門(mén)研究領(lǐng)域。IETF的6LoWPAN工作組致力于在IEEE 802.15.4標(biāo)準(zhǔn)上傳輸IPv6數(shù)據(jù)包，使得6LoWPAN網(wǎng)絡(luò)節(jié)點(diǎn)能夠利用IPv6地址實(shí)現(xiàn)互聯(lián)，并可接入互聯(lián)網(wǎng)。該工作組僅提出了適配層技術(shù)草案，其它技術(shù)還在探討中，其中6LoWPAN路由技術(shù)是亟待解決的關(guān)鍵技術(shù)之一。

現(xiàn)有的6LoWPAN路由協(xié)議主要有網(wǎng)狀路由和分級(jí)式路由。文獻(xiàn)［1］提出一個(gè)Mesh路由協(xié)議，它具有快速重路由能力，使網(wǎng)絡(luò)有很大的彈性，組網(wǎng)靈活;文獻(xiàn)［2］提出一個(gè)分級(jí)式路由協(xié)議，它根據(jù)事先定義的動(dòng)態(tài)地址分配算法實(shí)現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)，能可靠地在樹(shù)狀網(wǎng)絡(luò)中轉(zhuǎn)發(fā)數(shù)據(jù)，且不用建立和維護(hù)路由表。選擇哪一類路由協(xié)議應(yīng)根據(jù)不同應(yīng)用的要求來(lái)確定，如Mesh路由協(xié)議可用于大規(guī)模隨意布點(diǎn)的場(chǎng)合，組網(wǎng)速度快，且有一定的抗毀性。而分級(jí)路由協(xié)議適合于停車管理等場(chǎng)合，它能可靠地沿著一條路徑傳送數(shù)據(jù)。

本文針對(duì)6LoWPAN網(wǎng)絡(luò)的特性，分析其對(duì)路由協(xié)議的要求，設(shè)計(jì)了一種低開(kāi)銷的單播路由協(xié)議方案，并在NS－2中進(jìn)行了性能仿真，結(jié)果證明有效的實(shí)現(xiàn)了6LoWPAN網(wǎng)絡(luò)路由功能。

1 6LoWPAN網(wǎng)絡(luò)路由要求

一般6LoWPAN網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相對(duì)簡(jiǎn)單，規(guī)模相對(duì)較小，節(jié)點(diǎn)位置不固定，節(jié)點(diǎn)資源有限且長(zhǎng)期工作于睡眠模式，其底層硬件與其它無(wú)線通信具有較大的區(qū)別，故其路由協(xié)議不能直接使用傳統(tǒng)的自組網(wǎng)路由協(xié)議。

針對(duì)6LoWPAN網(wǎng)絡(luò)特點(diǎn)，設(shè)計(jì)路由協(xié)議時(shí)有以下要求:

第一，路由協(xié)議必須支持多種類型和角色的設(shè)備，如資源受限節(jié)點(diǎn)、網(wǎng)關(guān)、數(shù)據(jù)融合節(jié)點(diǎn)。

第二，為了應(yīng)對(duì)6LoWPAN網(wǎng)絡(luò)的低帶寬和高分組丟包率，路由載荷要盡量小以防止路由消息在物理層分片。根據(jù)不同的應(yīng)用層需求設(shè)計(jì)相應(yīng)的分組投遞率，根據(jù)不同的應(yīng)用層需求和IEEE802.15.4潛在的特性設(shè)計(jì)相應(yīng)的端到端數(shù)據(jù)通信性能?？煽刻幚碛捎趧?dòng)態(tài)發(fā)生的鏈路失效或節(jié)點(diǎn)無(wú)效引起的數(shù)據(jù)丟失。恰當(dāng)?shù)奶幚礞溌凡粚?duì)稱問(wèn)題，實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡。

第三，6LoWPAN支持不同的拓?fù)浜鸵?guī)模的網(wǎng)絡(luò)。路由協(xié)議需動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化。盡管一些節(jié)點(diǎn)周期性處于睡眠工作模式、路由協(xié)議仍然要可靠工作。需選取更好的路由權(quán)重以選出最優(yōu)路由。路由修復(fù)和相關(guān)的控制消息不能影響路由協(xié)議的總開(kāi)銷。路由協(xié)議需支持不同的通信模式(點(diǎn)對(duì)點(diǎn)，點(diǎn)對(duì)多點(diǎn)等)，避免過(guò)多的多播通信。

第四，為實(shí)現(xiàn)低開(kāi)銷，路由協(xié)議在MAC層之上、網(wǎng)絡(luò)層之下實(shí)現(xiàn)，這樣路由協(xié)議就用鏈路層地址來(lái)實(shí)現(xiàn)網(wǎng)內(nèi)的路由查找和報(bào)文轉(zhuǎn)發(fā)。

2 路由協(xié)議設(shè)計(jì)

2.1 設(shè)計(jì)方案

學(xué)術(shù)界提出了若干6LoWPAN路由方案，雖然都是輕量化的協(xié)議，但仍使用廣播方式查找路由，路由開(kāi)銷仍然較大。本文提出的路由協(xié)議是一種基于網(wǎng)狀拓?fù)涞钠矫娼Y(jié)構(gòu)按需式單播路由協(xié)議，工作在MAC層與IP層之間，特點(diǎn)如下:

第一，網(wǎng)絡(luò)中各節(jié)點(diǎn)在路由功能上地位相同，各節(jié)點(diǎn)都能參與路由并分擔(dān)傳輸流量，抗毀性強(qiáng)。

第二，按需式路由:可以降低路由開(kāi)銷，提高網(wǎng)絡(luò)吞吐量。

本協(xié)議僅有最基本的2個(gè)功能:路由發(fā)現(xiàn)、路由維護(hù)。路由的建立通過(guò)路由請(qǐng)求和路由回復(fù)過(guò)程實(shí)現(xiàn)，路由維護(hù)使用路由出錯(cuò)報(bào)文實(shí)現(xiàn)。

協(xié)議采用精簡(jiǎn)的路由表和多跳轉(zhuǎn)發(fā)的方式轉(zhuǎn)發(fā)分組，并采用簡(jiǎn)化的路由報(bào)文格式，且路由請(qǐng)求和回復(fù)報(bào)文格式相同。協(xié)議不使用最短路徑路由算法，而使用傳感器網(wǎng)絡(luò)特有的鏈路質(zhì)量LQI作為路由權(quán)重。使用802.15.4 MAC層特有的ACK機(jī)制來(lái)保證路由的可達(dá)性。協(xié)議依賴于對(duì)稱性的鏈路，不能處理非對(duì)稱性鏈路的網(wǎng)絡(luò)。協(xié)議取消常用的路由本地修復(fù)功能和周期性的hello消息發(fā)送，使協(xié)議更優(yōu)化，開(kāi)銷更小。

2.2 路由算法流程

當(dāng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)，首先節(jié)點(diǎn)構(gòu)造一個(gè)路由請(qǐng)求報(bào)文RERQ并通過(guò)IEEE802.15.4鏈路層多播廣播此消息，RERQ沿所有可能的鏈路傳遍整個(gè)網(wǎng)絡(luò)以發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn)，它經(jīng)過(guò)的每一個(gè)中間結(jié)點(diǎn)生成一條到源結(jié)點(diǎn)的路由。當(dāng)目的節(jié)點(diǎn)收到后，構(gòu)造一個(gè)路由回復(fù)報(bào)文RERP并單播給源節(jié)點(diǎn)。RREP經(jīng)過(guò)的每個(gè)中間結(jié)點(diǎn)均會(huì)建立到目的結(jié)點(diǎn)的路由。本協(xié)議只有目的節(jié)點(diǎn)才能構(gòu)造RREP，中間節(jié)點(diǎn)即便有到目的節(jié)點(diǎn)的路由，也會(huì)廣播RREQ，由此可避免循環(huán)問(wèn)題和無(wú)效RREP，提高了傳輸效率。當(dāng)源節(jié)點(diǎn)收到該RERP消息，就在源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)之間建立了一條雙向路由。源節(jié)點(diǎn)就能依據(jù)此路由發(fā)送數(shù)據(jù)，發(fā)送過(guò)程中若該路由不可達(dá)，中間節(jié)點(diǎn)就構(gòu)造并發(fā)送一個(gè)RERR給源節(jié)點(diǎn)，以通知鏈路失效。源節(jié)點(diǎn)收到RERR后，若數(shù)據(jù)未發(fā)送完，則重新發(fā)起一個(gè)RERQ進(jìn)行新的路由查找。

2.3 路由報(bào)文

路由消息包括RERQ，RREP和RERR。每個(gè)路由節(jié)點(diǎn)維護(hù)一個(gè)路由表，其表項(xiàng)是一個(gè)向量v=(D，S，N，W，T1，T2)，其中D 表示目的節(jié)點(diǎn)，S 為源節(jié)點(diǎn)，N為下一跳，W 為從路由權(quán)重，T1為該表項(xiàng)的無(wú)效時(shí)間，T2為該表項(xiàng)的刪除時(shí)間。若當(dāng)前時(shí)間超過(guò)T1，相應(yīng)的路由失效。若當(dāng)前時(shí)間超過(guò)T2，相應(yīng)的路由從路由表中刪掉。RERP和RERQ格式相似，如圖1所示。

其中，type標(biāo)識(shí)路由報(bào)文的類型，1是RERQ，2是RERP。TTL是消息轉(zhuǎn)發(fā)的最長(zhǎng)時(shí)間。Metric是路由權(quán)重LQI值。S是消息的發(fā)起節(jié)點(diǎn)。對(duì)于RERQ，S是產(chǎn)生RERQ的節(jié)點(diǎn)地址，對(duì)于RERP，S是回答RERQ的節(jié)點(diǎn)地址。D是被查找節(jié)點(diǎn)的地址。ID是一個(gè)RREQ的標(biāo)識(shí)，它保證節(jié)點(diǎn)之間只對(duì)一個(gè)RREQ進(jìn)行一次處理，并與一個(gè)特定的RREQ所對(duì)應(yīng)的RREP匹配［5］。

RERR報(bào)文格式較簡(jiǎn)單，主要包括:類型標(biāo)識(shí)、產(chǎn)生RERR的節(jié)點(diǎn)、RERR發(fā)往的目的節(jié)點(diǎn)及導(dǎo)致產(chǎn)生RERR的故障節(jié)點(diǎn)地址。

2.4 路由查找和維護(hù)流程

當(dāng)節(jié)點(diǎn)轉(zhuǎn)發(fā)IPv6報(bào)文時(shí)，先判斷是否是廣播報(bào)文。如果是，則向自己的鄰居轉(zhuǎn)發(fā)。否則，依據(jù)目的地址查路由表，若找到路由則轉(zhuǎn)發(fā)此報(bào)文。反之，備份IPv6報(bào)文，新建一個(gè)RERQ并廣播出去，并修改RREQ ID以記錄該節(jié)點(diǎn)轉(zhuǎn)發(fā)了一次RERQ消息。節(jié)點(diǎn)收到需要的RERP之前不再發(fā)送RERQ。節(jié)點(diǎn)收到RERP后，按照所獲得的路由轉(zhuǎn)發(fā)IPv6報(bào)文。若在預(yù)期內(nèi)未收到RERP，節(jié)點(diǎn)重新創(chuàng)建一個(gè)RERQ進(jìn)行路由查找，預(yù)期內(nèi)仍未收到RERP，則認(rèn)為路徑不可達(dá)，IPv6報(bào)文無(wú)法發(fā)送。路由查找流程如圖2所示。

圖2 路由查找流程

圖3 RERQ處理流程

當(dāng)中間節(jié)點(diǎn)收到RERQ時(shí)，先檢查自己的路由表，根據(jù)RERQ中的源節(jié)點(diǎn)地址判斷是否有相應(yīng)的條目。若沒(méi)有，創(chuàng)建一個(gè)新的條目。否則，比較消息中的路由權(quán)重和已有的條目中的相應(yīng)值，若消息中的值大，丟棄該RREQ。反之，根據(jù)消息中的內(nèi)容更新該路由表?xiàng)l目。然后，中間節(jié)點(diǎn)判斷RREQ是否是給自己的，若是則向源節(jié)點(diǎn)單播一個(gè)RERP。若不是，則查找路由表相應(yīng)條目將消息轉(zhuǎn)發(fā)出去，找不到相應(yīng)的路由則向該中間節(jié)點(diǎn)的鄰居廣播RERQ。詳細(xì)流程如圖3所示。

為了對(duì)網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化做出反應(yīng)，結(jié)點(diǎn)要維護(hù)它們的路由，監(jiān)視它們的鏈路。實(shí)現(xiàn)方法如下:在使用一條路由轉(zhuǎn)發(fā)IPv6報(bào)文之前，必須對(duì)該條路由進(jìn)行有效性檢測(cè)。若當(dāng)前時(shí)間超過(guò)路由的ValidTimeout，則報(bào)文無(wú)法轉(zhuǎn)發(fā)，隨之新建一個(gè)RERR，以通知源節(jié)點(diǎn)該路由已經(jīng)失效。如果當(dāng)前時(shí)間超過(guò)路由的刪除時(shí)間，則刪除路由。節(jié)點(diǎn)還需對(duì)所有使用該失效鏈路的路由的無(wú)效時(shí)間設(shè)為當(dāng)前時(shí)間。

3 協(xié)議性能仿真

3.1 仿真模型

本文用NS－2對(duì)設(shè)計(jì)的協(xié)議進(jìn)行仿真。IEEE 802.15.4模型使用CUNY提供的MAC仿真模塊實(shí)現(xiàn)。仿真中設(shè)置一個(gè)100m×100m范圍的mesh多跳網(wǎng)絡(luò)，該區(qū)域隨機(jī)分布50個(gè)結(jié)點(diǎn)。網(wǎng)絡(luò)中有1個(gè)PAN節(jié)點(diǎn)和若干個(gè)coordinator節(jié)點(diǎn)和設(shè)備節(jié)點(diǎn)，仿真時(shí)間300秒。PAN節(jié)點(diǎn)和coordinator節(jié)點(diǎn)均為FFD，設(shè)備節(jié)點(diǎn)是RFD，每個(gè)節(jié)點(diǎn)的間距都是10米，每個(gè)節(jié)點(diǎn)的傳輸距離是13米。節(jié)點(diǎn)間傳輸數(shù)據(jù)速率是250Kbps。仿真中使用的報(bào)文發(fā)送的分布概率分布是泊松流量，平均報(bào)文速率是1pps。應(yīng)用層的報(bào)文大小是250byte，無(wú)線傳播模型都是two－way－ground模型。在所有的FFD節(jié)點(diǎn)上依次設(shè)置設(shè)置本路由協(xié)議。隨機(jī)產(chǎn)生20個(gè)節(jié)點(diǎn)向一個(gè)PAN發(fā)送數(shù)據(jù)包。

3.2 仿真結(jié)果及分析

路由協(xié)議分析常用的性能指標(biāo)有很多，限于篇幅，本文僅對(duì)平均端到端時(shí)延、分組投遞率和路由開(kāi)銷進(jìn)行仿真。通過(guò)大量仿真實(shí)驗(yàn)，處理數(shù)據(jù)后可以得到本協(xié)議和現(xiàn)有6LoWPAN網(wǎng)絡(luò)路由協(xié)議LOAD的性能對(duì)比。結(jié)果表明:本協(xié)議的路由開(kāi)銷較小，降低了網(wǎng)絡(luò)中端到端的數(shù)據(jù)延遲時(shí)間，兩種協(xié)議的分組傳送率相近。

圖4中，協(xié)議的路由開(kāi)銷隨著節(jié)點(diǎn)停留時(shí)間的延長(zhǎng)而降低，這說(shuō)明當(dāng)節(jié)點(diǎn)減少移動(dòng)后，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)變化趨慢，路由查找和維護(hù)的報(bào)文減少。而且，本協(xié)議的路由開(kāi)銷相對(duì)較少，這是因?yàn)閰f(xié)議采用精簡(jiǎn)的路由報(bào)文格式、簡(jiǎn)化路由查找算法、且沒(méi)有使用周期性的廣播報(bào)文hello以及限制RREP，只能由目的節(jié)點(diǎn)構(gòu)造等優(yōu)化設(shè)計(jì)帶來(lái)的效果。

圖4 路由開(kāi)銷

圖5 平均端到端時(shí)延結(jié)果

圖5中，隨著節(jié)點(diǎn)的停留時(shí)間增大，兩種協(xié)議的平均端到端時(shí)延都減小。這是因?yàn)殡S著節(jié)點(diǎn)停留時(shí)間增大，節(jié)點(diǎn)減少移動(dòng)，各種路由消息(RREQ、RREP)和路由維護(hù)報(bào)文RRER減少，故減少了路由發(fā)現(xiàn)操作的頻度所導(dǎo)致的延時(shí)及因路由不可達(dá)而造成的丟包帶來(lái)的傳輸時(shí)延。

圖6表明，數(shù)據(jù)分組的投遞率隨節(jié)點(diǎn)停留時(shí)間增加而增大，這是因?yàn)殡S著節(jié)點(diǎn)停留時(shí)間增大，節(jié)點(diǎn)減少移動(dòng)，路由信息變化變慢，路由維護(hù)開(kāi)銷減少，故減少了因路由不可達(dá)而造成的丟包。

4 結(jié)論

本文詳細(xì)分析6LoWPAN網(wǎng)絡(luò)路由協(xié)議的要求，詳細(xì)設(shè)計(jì)了一種高效的低開(kāi)銷按需路由協(xié)議。仿真和實(shí)驗(yàn)結(jié)果表明，該協(xié)議具有簡(jiǎn)單性、低網(wǎng)絡(luò)延遲、低開(kāi)銷以及較高的分組投遞率，能較好地適應(yīng)6LoWPAN網(wǎng)絡(luò)拓?fù)渥兓?。該協(xié)議目前還不盡完善，改進(jìn)協(xié)議性能的進(jìn)一步實(shí)驗(yàn)和測(cè)試正在進(jìn)行中。

［1］Montenegro G，Yoo S，Kushalnagar N.6LoWPAN Ad Hoc On－Demand Distance Vector Routing(LOAD)［EB/OL］.http://tools.ietf.org/wg/6lowpan，2007.6.19.

［2］KIM K，YOO S，PARK D.Hierarchical Routing over 6LoWPAN(HiLow)［EB/OL］.http://www.vsix.net/other/summit/Korea2006/www.ipv6.or.kr/summit2006/proceeding/TS123.pdf，2006.4.

［3］Kim E，Kaspar D，Gomez C.Problem Statement and Requirements for 6LoWPAN Routing［EB/OL］.http://tools.ietf.org/wg/6lowpan/draft－ietf－6lowpan－routing－ requirements/，2008.11.18.

［4］KIM H，HONG C，OKAMURA K.A routing scheme for sup－porting network mobility of sensor network based on 6LoWPAN［C］.Proceedings of 10th Asia－Pacific Network Operations and Management Symposium:APNOMS 2007，LNCS 4773.Berlin:Springer－Verlag，2007:155－164.

［5］Kim K，Montenegro G，Daniel Park S，etc.Dynamic MANET On－demand for 6LoWPAN(DYMO－low)Routing［EB/OL］.http://www.ietf.org/ietf/1id－ abstracts.txt，2005.10.16.