一種基于微型無(wú)線傳感網(wǎng)絡(luò)的路由算法

　　2 MSAODV 路由算法的基本思想與算法原理

　　2.1 路由算法的基本思想

　　在研究了 AODV 路由協(xié)議之后,本文提出了一種全新的路由算法,這種路由算法適合在 微型無(wú)線傳感器網(wǎng)絡(luò)上使用,又由于是基于AODV 路由協(xié)議之上,故稱之為MSAODV(Micro- Sensor Ad-hoc On-Demand Distance Vector Algorithm)路由協(xié)議。

　　無(wú)線傳感器網(wǎng)絡(luò)與傳統(tǒng)無(wú)線移動(dòng)網(wǎng)絡(luò)有區(qū)別,無(wú)線傳感器網(wǎng)絡(luò)最關(guān)心的是整個(gè)網(wǎng)絡(luò)的成 存周期,而傳統(tǒng)無(wú)線移動(dòng)網(wǎng)主要關(guān)心的是網(wǎng)絡(luò)拓?fù)?br />網(wǎng)絡(luò)拓?fù)?p>　　通常將網(wǎng)絡(luò)中的主機(jī)、終端和其他通信控制與處理設(shè)備抽象為結(jié)點(diǎn)；將通信線路抽象為線路，而將結(jié)點(diǎn)和線路連接而成的幾何圖形稱為網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以反映出網(wǎng)絡(luò)中各實(shí)體之間的結(jié)構(gòu)關(guān)系。

變化情況下可靠傳輸質(zhì)量。微型無(wú)線傳感 器網(wǎng)絡(luò)中的節(jié)點(diǎn)具有體積小,功耗小,通信距離短等特點(diǎn),他們應(yīng)用的場(chǎng)合非常廣泛,像戰(zhàn)場(chǎng)敵 方信息采集,森林火災(zāi)監(jiān)控等,這些場(chǎng)合往往是一些無(wú)人區(qū),傳感器節(jié)點(diǎn)拋撒到這些地方再回 收的可能性非常小,所以節(jié)點(diǎn)的功耗決定了他的使用時(shí)間。針對(duì)這些特點(diǎn),MSAODV 路由算 法采用了按需查詢方式,他簡(jiǎn)單實(shí)用,易于擴(kuò)充,協(xié)議開(kāi)銷小,應(yīng)用了這種路由算法傳感器節(jié)點(diǎn) 大部分時(shí)間都可以處在睡眠狀態(tài),這樣就延長(zhǎng)了節(jié)點(diǎn)的使用時(shí)間,適合無(wú)線傳感器網(wǎng)絡(luò)的使用 環(huán)境。

　　2.2 MSAODV 路由算法原理

　　MSAODV 路由協(xié)議算法是在AODV 路由協(xié)議的基礎(chǔ)上改進(jìn)演化而來(lái)的,他繼承了AODV 路由算法的許多特點(diǎn),但是又與AODV 路由協(xié)議算法有所不同。無(wú)線傳感器網(wǎng)絡(luò)的體 系結(jié)構(gòu)將有助于設(shè)計(jì)MSAODV 路由協(xié)議算法,圖1 顯示了無(wú)線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)。

　　MSAODV 路由算法同樣假設(shè)網(wǎng)絡(luò)中的所有鏈路都是雙向?qū)ΨQ的,即某個(gè)源節(jié)點(diǎn)通過(guò)一 條路由可以到達(dá)無(wú)線網(wǎng)絡(luò)中的某個(gè)目的節(jié)點(diǎn)時(shí),該目的節(jié)點(diǎn)同樣也可以通過(guò)這條路由的反向 路由回到源節(jié)點(diǎn)。MSAODV 路由協(xié)議同樣是一種按需的距離向量路由協(xié)議,具有按需路由協(xié) 議的特點(diǎn),網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)在需要進(jìn)行通信時(shí)才發(fā)送路由分組,而不會(huì)周期性地交互路由信 息以得到所有其它主機(jī)的路由:同時(shí)具有距離向量路由協(xié)議的一些特點(diǎn),即各節(jié)點(diǎn)路由表只維 護(hù)本節(jié)點(diǎn)到其他節(jié)點(diǎn)的路由,而無(wú)須掌握全網(wǎng)拓?fù)浣Y(jié)構(gòu)。

　　MSAODV 路由協(xié)議中只有兩種類型的消息控制幀:路由請(qǐng)求RREQ 和路由應(yīng)答RREP。 和AODV 路由協(xié)議一樣,當(dāng)源節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)而又沒(méi)有到目的節(jié)點(diǎn)的有效路由時(shí),啟動(dòng)一 個(gè)路由發(fā)現(xiàn)過(guò)程:向網(wǎng)絡(luò)廣播一個(gè)路由請(qǐng)求包RREQ,中間節(jié)點(diǎn)轉(zhuǎn)發(fā)該路由請(qǐng)求,收到請(qǐng)求的目 的節(jié)點(diǎn)以單播的方式向源節(jié)點(diǎn)返回一個(gè)RREP 包,RREP 沿著剛建立的逆向路徑傳輸回源節(jié) 點(diǎn),源節(jié)點(diǎn)收到該RREP 包后則開(kāi)始向?qū)?yīng)目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)。在路由請(qǐng)求包的正向傳播過(guò) 程中,網(wǎng)絡(luò)中能收到該路由請(qǐng)求的節(jié)點(diǎn)都建立起了到源節(jié)點(diǎn)的反向路由,當(dāng)目的節(jié)點(diǎn)收到路由 請(qǐng)求而回送路由應(yīng)答時(shí),逆向路徑上的節(jié)點(diǎn)又建立了前向路由。整個(gè)MSAODV 路由發(fā)現(xiàn)過(guò) 程如圖2 所示,a 圖表示的是反向路由的建立過(guò)程,節(jié)點(diǎn)S 需要和節(jié)點(diǎn)D 通信,但是他沒(méi)有節(jié)點(diǎn) D 的路由,所以節(jié)點(diǎn)S 發(fā)起到節(jié)點(diǎn)D 的路由請(qǐng)求,節(jié)點(diǎn)S 廣播一個(gè)路由請(qǐng)求包,收到路由請(qǐng)求包 的節(jié)點(diǎn)轉(zhuǎn)發(fā)節(jié)點(diǎn)S 的請(qǐng)求,最終節(jié)點(diǎn)D 收到了節(jié)點(diǎn)S 的路由請(qǐng)求包,這個(gè)過(guò)程建立了節(jié)點(diǎn)S 到 節(jié)點(diǎn)D 的反向路由;b 圖表示的是由節(jié)點(diǎn)S 到節(jié)點(diǎn)D 前向路由的建立過(guò)程,當(dāng)節(jié)點(diǎn)D 收到節(jié)點(diǎn) S 的路由請(qǐng)求包后,他要給節(jié)點(diǎn)S 回送一個(gè)路由應(yīng)答包,順著剛才建立的反向路由,應(yīng)答包最終 被節(jié)點(diǎn)S 成功接收,在此過(guò)程中節(jié)點(diǎn)S 又建立了到節(jié)點(diǎn)D 的前向路由。

　　3 MSAODV 路由中的路由表與協(xié)議幀的格式

　　3.1 MSAODV 路由協(xié)議路由表

　　網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都有這樣的一個(gè)路由表,該表保存了對(duì)應(yīng)節(jié)點(diǎn)的路由信息,由于各個(gè) 節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置不同,因而他們的路由表項(xiàng)也不相同,例如在圖2(b)中,a 節(jié)點(diǎn)的路由表有 兩項(xiàng),c 節(jié)點(diǎn)的路由表也有兩項(xiàng),如表1 所示。

　　3.2 MSAODV 路由協(xié)議幀格式

　　由于 MSAODV 路由協(xié)議是AODV 路由協(xié)議的改進(jìn)演化,所以與AODV 路由協(xié)議幀類 似,MSAODV 路由協(xié)議也包括RR 衛(wèi)Q 協(xié)議幀和RREP 協(xié)議幀,但不包含RERR 協(xié)議幀。不 包含RERR 協(xié)議幀會(huì)導(dǎo)致MSAODV 協(xié)議在路由維護(hù)和錯(cuò)誤處理上功能欠缺,但可以通過(guò)其 他方法來(lái)彌補(bǔ)這個(gè)缺陷。

　　1 RREQ 協(xié)議幀格式

　　RREQ 路由請(qǐng)求協(xié)議幀如表2 所示。