MSAODV路由算法的原理及在無線傳感器網(wǎng)絡(luò)方面的應(yīng)用-設(shè)計(jì)應(yīng)用

精品文檔-下載后可編輯MSAODV路由算法的原理及在無線傳感器網(wǎng)絡(luò)方面的應(yīng)用-設(shè)計(jì)應(yīng)用2MSAODV路由算法的基本思想與算法原理2.1路由算法的基本思想在研究了AODV路由協(xié)議之后，本文提出了一種全新的路由算法，這種路由算法適合在微型無線傳感器網(wǎng)絡(luò)上使用，又由于是基于AODV路由協(xié)議之上，故稱之為MSAODV（Micro-SensorAd-hocOn-DemandDistanceVectorAlgorithm）路由協(xié)議。無線傳感器網(wǎng)絡(luò)與傳統(tǒng)無線移動(dòng)網(wǎng)絡(luò)有區(qū)別，無線傳感器網(wǎng)絡(luò)關(guān)心的是整個(gè)網(wǎng)絡(luò)的成存周期，而傳統(tǒng)無線移動(dòng)網(wǎng)主要關(guān)心的是網(wǎng)絡(luò)拓?fù)渥兓闆r下可靠傳輸質(zhì)量。微型無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)具有體積小，功耗小，通信距離短等特點(diǎn)，他們應(yīng)用的場(chǎng)合非常廣泛，像戰(zhàn)場(chǎng)敵方信息采集，森林火災(zāi)監(jiān)控等，這些場(chǎng)合往往是一些無人區(qū)，傳感器節(jié)點(diǎn)拋撒到這些地方再回收的可能性非常小，所以節(jié)點(diǎn)的功耗決定了他的使用時(shí)間。針對(duì)這些特點(diǎn)，MSAODV路由算法采用了按需查詢方式，他簡(jiǎn)單實(shí)用，易于擴(kuò)充，協(xié)議開銷小，應(yīng)用了這種路由算法傳感器節(jié)點(diǎn)大部分時(shí)間都可以處在睡眠狀態(tài)，這樣就延長(zhǎng)了節(jié)點(diǎn)的使用時(shí)間，適合無線傳感器網(wǎng)絡(luò)的使用環(huán)境。2.2MSAODV路由算法原理MSAODV路由協(xié)議算法是在AODV路由協(xié)議的基礎(chǔ)上改進(jìn)演化而來的，他繼承了AODV路由算法的許多特點(diǎn)，但是又與AODV路由協(xié)議算法有所不同。無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)將有助于設(shè)計(jì)MSAODV路由協(xié)議算法，圖1顯示了無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)。

MSAODV路由算法同樣假設(shè)網(wǎng)絡(luò)中的所有鏈路都是雙向?qū)ΨQ的，即某個(gè)源節(jié)點(diǎn)通過一條路由可以到達(dá)無線網(wǎng)絡(luò)中的某個(gè)目的節(jié)點(diǎn)時(shí)，該目的節(jié)點(diǎn)同樣也可以通過這條路由的反向路由回到源節(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ǎng)拓?fù)浣Y(jié)構(gòu)。MSAODV路由協(xié)議中只有兩種類型的消息控制幀：路由請(qǐng)求RREQ和路由應(yīng)答RREP。和AODV路由協(xié)議一樣，當(dāng)源節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)而又沒有到目的節(jié)點(diǎn)的有效路由時(shí)，啟動(dòng)一個(gè)路由發(fā)現(xiàn)過程：向網(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包后則開始向?qū)?yīng)目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)。在路由請(qǐng)求包的正向傳播過程中，網(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)過程如圖2所示，a圖表示的是反向路由的建立過程，節(jié)點(diǎn)S需要和節(jié)點(diǎn)D通信，但是他沒有節(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è)過程建立了節(jié)點(diǎn)S到節(jié)點(diǎn)D的反向路由；b圖表示的是由節(jié)點(diǎn)S到節(jié)點(diǎn)D前向路由的建立過程，當(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成功接收，在此過程中節(jié)點(diǎn)S又建立了到節(jié)點(diǎn)D的前向路由。MSAODV路由算法的原理及在無線傳感器網(wǎng)絡(luò)方面的應(yīng)用3MSAODV路由中的路由表與協(xié)議幀的格式3.1MSAODV路由協(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.2MSAODV路由協(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ò)誤處理上功能欠缺，但可以通過其他方法來彌補(bǔ)這個(gè)缺陷。RREQ協(xié)議幀格式RREQ路由請(qǐng)求協(xié)議幀如表2所示。

RREP協(xié)議幀格式RREP路由應(yīng)答協(xié)議幀如表3所示。

4MSAODV路由協(xié)議的操作由于MSAODV路由協(xié)議是對(duì)AODV協(xié)議的改進(jìn)演化，所以MSAODV路由協(xié)議的操作與AODV路由協(xié)議的操作大同小異，為了清晰起見，對(duì)MSAODV協(xié)議的操作做一詳細(xì)的介紹還是有必要的。4.1產(chǎn)生路由請(qǐng)求無線網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)需要和網(wǎng)絡(luò)中的另一個(gè)節(jié)點(diǎn)通信時(shí)，他首先會(huì)查找自己的路由表，以確定是否有通往該目的節(jié)點(diǎn)的有效路由，如果有的話，從對(duì)應(yīng)的目的節(jié)點(diǎn)路由表項(xiàng)中取出下一跳節(jié)點(diǎn)地址，然后構(gòu)造數(shù)據(jù)包并把該數(shù)據(jù)包發(fā)往下一節(jié)點(diǎn)，如果不存在通往目的節(jié)點(diǎn)的路由，那么該節(jié)點(diǎn)就要發(fā)起路由請(qǐng)求。4.2處理和轉(zhuǎn)發(fā)路由請(qǐng)求處理和轉(zhuǎn)發(fā)路由請(qǐng)求是針對(duì)源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的中間節(jié)點(diǎn)而言。這些中間節(jié)點(diǎn)可能不止一個(gè)，在他們收到源節(jié)點(diǎn)廣播的RREQ路由請(qǐng)求幀之后，必需處理和轉(zhuǎn)發(fā)該路由請(qǐng)求幀。該RREQ請(qǐng)求幀是否己經(jīng)被成功接收過，判斷的依據(jù)就是源節(jié)點(diǎn)的IP地址和廣播ID號(hào)，如果發(fā)現(xiàn)由源節(jié)點(diǎn)和廣播ID標(biāo)志的RREQ請(qǐng)求幀是新的，也就是沒收到過，就會(huì)根據(jù)此RREQ請(qǐng)求幀更新自己路由表中對(duì)應(yīng)的項(xiàng)。很顯然，該路由表項(xiàng)的目的節(jié)點(diǎn)IP字段就是是源節(jié)點(diǎn)IP地址，下一跳IP地址就是發(fā)送此RREQ請(qǐng)求幀的節(jié)點(diǎn)IP地址，有可能是源節(jié)點(diǎn)也有可能是另一個(gè)中間節(jié)點(diǎn)。接下來此中間節(jié)點(diǎn)判斷該RREQ請(qǐng)求幀的目的IP是不是就是自己，如果是就回送一個(gè)RREP回應(yīng)幀，不是就轉(zhuǎn)發(fā)該RREQ請(qǐng)求幀。4.3產(chǎn)生路由應(yīng)答RREQ經(jīng)過中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)到達(dá)目的節(jié)點(diǎn)或者是直接到達(dá)目的節(jié)點(diǎn)后，目的節(jié)點(diǎn)要進(jìn)行相應(yīng)的處理。目的節(jié)點(diǎn)收到RREQ請(qǐng)求包，首先會(huì)判斷是否已經(jīng)收到過此請(qǐng)求包，如果沒有收到過則更新自己相應(yīng)的路由表項(xiàng)，目的節(jié)點(diǎn)把該路由表項(xiàng)的目的IP更新為源節(jié)點(diǎn)的IP地址，下一跳IP為發(fā)給他RR衛(wèi)Q請(qǐng)求幀的節(jié)點(diǎn)IP,目的節(jié)點(diǎn)序列號(hào)填上源節(jié)點(diǎn)的序列號(hào)，該序列號(hào)在RREQ請(qǐng)求幀里，跳數(shù)直接從RREQ請(qǐng)求幀里拷貝。在確認(rèn)請(qǐng)求的節(jié)點(diǎn)就是自己后，目的節(jié)點(diǎn)要給源節(jié)點(diǎn)發(fā)送一個(gè)RREP應(yīng)答幀，接下來目的節(jié)點(diǎn)構(gòu)造一個(gè)RREP應(yīng)答幀并正確初始化該幀。類型字段為2,表示該幀是RREP應(yīng)答幀。跳數(shù)字段為0,因?yàn)槭悄康墓?jié)點(diǎn)發(fā)起的RREP應(yīng)答幀。目的節(jié)點(diǎn)產(chǎn)生一個(gè)RREP應(yīng)答包之前，必需更新自己的序列號(hào)，更新值為當(dāng)前序列號(hào)與RREQ請(qǐng)求包中的目的序列號(hào)兩者中的值，目的序列號(hào)字段被初始化為這個(gè)值。源IP地址指的是發(fā)起RREQ請(qǐng)求幀的源節(jié)點(diǎn)的IP地址，而不是指目的節(jié)點(diǎn)的IP地址，同樣的，目的IP地址就是目的節(jié)點(diǎn)的IP地址，也就是發(fā)起RREP應(yīng)答幀的節(jié)點(diǎn)IP地址。在目的節(jié)點(diǎn)構(gòu)造好RREP回應(yīng)幀后，就要把該幀以單播的形式沿著反向路由傳送，他的下一跳節(jié)點(diǎn)IP地址是發(fā)給他RREQ請(qǐng)求幀的節(jié)點(diǎn)地址，可能是某個(gè)中間節(jié)點(diǎn)，也可能是源節(jié)點(diǎn)。一切準(zhǔn)備就緒，目的節(jié)點(diǎn)按照退避算法發(fā)送該幀。4.4接收和轉(zhuǎn)發(fā)路由應(yīng)答由于無線網(wǎng)絡(luò)的特點(diǎn)，盡管目的節(jié)點(diǎn)是以單播的形式向源節(jié)點(diǎn)回送RREP回應(yīng)幀，但是網(wǎng)絡(luò)中的很多節(jié)點(diǎn)也能接收到該幀，當(dāng)然，這些節(jié)點(diǎn)只是簡(jiǎn)單的丟棄該幀，只有反向路由上的節(jié)點(diǎn)才會(huì)接收該RREP回應(yīng)幀。反向路由上的節(jié)點(diǎn)會(huì)沿著反向路由順利的把RREP回應(yīng)幀傳給源節(jié)點(diǎn)，同時(shí)他們也根據(jù)此RREP回應(yīng)幀建立了前向路由。該節(jié)點(diǎn)下面要完成的工作就是把該RREP回應(yīng)幀轉(zhuǎn)發(fā)出去。他要知道下一跳節(jié)點(diǎn)的IP地址，以RREP回應(yīng)幀中的源節(jié)點(diǎn)IP地址為關(guān)鍵字查找路由表，得到下一跳節(jié)點(diǎn)的IP,這個(gè)表項(xiàng)是在建立反向路由時(shí)建立或更新的。該中間節(jié)點(diǎn)在完成上面的步驟后，以退避算法轉(zhuǎn)發(fā)該RREP回應(yīng)幀。與RREQ請(qǐng)求幀的轉(zhuǎn)發(fā)不同，R.REP回應(yīng)幀的轉(zhuǎn)發(fā)是單播的，他不會(huì)像R.REQ請(qǐng)求幀那樣可能被轉(zhuǎn)發(fā)多次，所以R.REP回應(yīng)幀的字段里不存在廣播ID。4.5新節(jié)點(diǎn)加入無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)在開機(jī)或重啟之后，會(huì)向網(wǎng)絡(luò)廣播一個(gè)RESET消息，網(wǎng)絡(luò)中的其他節(jié)點(diǎn)收到此RESET消息后會(huì)轉(zhuǎn)發(fā)該幀，主節(jié)點(diǎn)收到該幀。新節(jié)點(diǎn)在RESET消息幀里攜帶自己的IP地址，這樣當(dāng)主節(jié)點(diǎn)收到該幀后就可以知道是哪個(gè)節(jié)點(diǎn)重啟。收到RESET消息幀的其他節(jié)點(diǎn)首先查找自己的路由表看是否有主節(jié)點(diǎn)的IP地址，如果有就以單播的形式發(fā)送該幀，反之則繼續(xù)廣播此RESET消息幀。每個(gè)節(jié)點(diǎn)都要保存上他收到的RESET消息幀中的源節(jié)點(diǎn)IP地址，下次再收到RESE