[發(fā)明專利]一種基于平面區(qū)域劃分的Ad Hoc網(wǎng)絡(luò)多徑路由方法

有效

• 申請?zhí)枺?/td>: 201210014693.0
• 申請日: 2012-01-18
• 公開（公告）號: CN102547902A
• 公開（公告）日: 2012-07-04
• 發(fā)明（設(shè)計）人: 蘭少華;魏曉飛;董萍;吳歉歉;楊余旺;符意德
• 申請（專利權(quán)）人: 南京理工大學(xué)
• 主分類號: H04W40/02
• 分類號: H04W40/02
• 代理公司: 南京理工大學(xué)專利中心 32203
• 代理人: 朱顯國

技術(shù)領(lǐng)域

本發(fā)明涉及計算機(jī)網(wǎng)絡(luò)技術(shù)領(lǐng)域的Ad?Hoc網(wǎng)絡(luò)多徑路由方法，特別是一種基于平面區(qū)域劃分的Ad?Hoc網(wǎng)絡(luò)多徑路由方法。?

背景技術(shù)

Ad?Hoc網(wǎng)絡(luò)(自組織網(wǎng)絡(luò))是不依賴于任何固定基礎(chǔ)設(shè)施的移動節(jié)點(diǎn)的動態(tài)聯(lián)合體。由于具有無需基礎(chǔ)設(shè)施支持、高動態(tài)性、無線通信以及多跳傳輸?shù)母吒采w性等優(yōu)點(diǎn)，Ad?Hoc網(wǎng)絡(luò)在軍事應(yīng)用、災(zāi)難援助等領(lǐng)域具有廣泛的應(yīng)用前景。然而，Ad?Hoc網(wǎng)絡(luò)本身具有的高動態(tài)性、多跳傳輸、能量有限性等特點(diǎn)使得保障可靠的數(shù)據(jù)傳輸成為一個關(guān)鍵而棘手的問題。?

相對于傳統(tǒng)的單徑路由，多徑路由在實現(xiàn)負(fù)載均衡、提高路由可靠性和容錯性方面具有很強(qiáng)的優(yōu)勢，已成為自組織網(wǎng)絡(luò)路由研究中的熱點(diǎn)。多徑路由實現(xiàn)是Ad?Hoc網(wǎng)絡(luò)可靠運(yùn)行的有效保證。多徑路由利用多條鏈路的冗余，提高動態(tài)變化系統(tǒng)的可靠性。此外，在一次路由發(fā)現(xiàn)過程中找到多條路徑，能夠減少路由發(fā)現(xiàn)次數(shù)，并降低傳統(tǒng)的差錯控制開銷與端到端延時，提高網(wǎng)絡(luò)實時性。使用多徑之后，將原本集中在一條路徑上的負(fù)載分配到了幾條不同的路徑上，減少了該路徑上中間節(jié)點(diǎn)的能量消耗，也有利于提高實時性。多徑路由可以適應(yīng)無線網(wǎng)絡(luò)中節(jié)點(diǎn)易失效的特點(diǎn)，從而較好地利用網(wǎng)絡(luò)拓?fù)湫畔ⅰ?

多徑技術(shù)按照多徑使用方式分成依次使用單條路徑和并發(fā)使用多條路徑模式，按照路徑相互關(guān)系分成相交多徑、鏈路不相交多徑和節(jié)點(diǎn)不相交多徑模型。節(jié)點(diǎn)不相交多徑最能充分利用網(wǎng)絡(luò)資源，達(dá)到負(fù)載均衡，但是也最難尋找。?

目前的多徑路由一般是在單路徑路由(如動態(tài)源路由協(xié)議DSR和自組織網(wǎng)絡(luò)按需距離矢量路由協(xié)議AODV)的基礎(chǔ)上進(jìn)行擴(kuò)展，如：分離多徑路由(split?multipath?routing，SMR)，按需多徑距離矢量路由(ad?hoc?on-demand?multipath?distance?vector，AOMDV)，基于選票方式的路由協(xié)議(ticket?based?routing?protocol，TBR)。這幾種典型的多徑路由協(xié)議在應(yīng)用于大規(guī)模的網(wǎng)絡(luò)環(huán)境中會存在廣播風(fēng)暴的問題，而且現(xiàn)有的大多數(shù)路由方法也沒有充分地利用節(jié)點(diǎn)的地理位置信息來尋找多條路經(jīng)。?

發(fā)明內(nèi)容

本發(fā)明目的在于提供一種快速建立最大限度不相交多徑的路由算法。?

實現(xiàn)本發(fā)明目的的技術(shù)解決方案為：?

1)源節(jié)點(diǎn)計算自身與目的節(jié)點(diǎn)之間的距離，將網(wǎng)絡(luò)中所有節(jié)點(diǎn)所在的平面通過橢圓曲線劃分成不相交的區(qū)域，根據(jù)需要的路徑條數(shù)確定區(qū)域的個數(shù)以及相應(yīng)的曲線條數(shù)，然后計算各個曲線方程的系數(shù)；?

2)源節(jié)點(diǎn)將自身與目的節(jié)點(diǎn)的地理位置信息，以及曲線方程系數(shù)寫入數(shù)據(jù)包頭部，并在數(shù)據(jù)包頭部添加訪問路徑字段，用來存儲局部的訪問路徑，然后根據(jù)路由轉(zhuǎn)發(fā)策略向下一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)；?

3)轉(zhuǎn)發(fā)節(jié)點(diǎn)收到數(shù)據(jù)包后，從包頭部取出源節(jié)點(diǎn)與目的節(jié)點(diǎn)的地理位置信息，以及曲線方程系數(shù)，判斷自身所在區(qū)域，并根據(jù)路由轉(zhuǎn)發(fā)策略繼續(xù)轉(zhuǎn)發(fā)；?

4)后續(xù)轉(zhuǎn)發(fā)節(jié)點(diǎn)按照步驟3所述方法繼續(xù)轉(zhuǎn)發(fā)，直至數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)。?

其中計算曲線方程系數(shù)的方法如下：?

1)計算源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的距離。源節(jié)點(diǎn)S通過位置服務(wù)(Location?Service)獲得目的節(jié)點(diǎn)D的地理位置坐標(biāo)D(x_D，y_D)，源節(jié)點(diǎn)S的地理位置坐標(biāo)是S(x_S，y_S)。通過兩點(diǎn)之間的距離公式計算源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的距離?d=(xD-xS)2+(yD-yS)2.]]>

2)確定需要的曲線條數(shù)。當(dāng)路徑條數(shù)為k時，需要?條曲線，這里將直線y＝0和橢圓曲線?統(tǒng)稱為曲線，當(dāng)a，b等于0時，曲線方程為y＝0。?