通信工程tang譯文

1、移動(dòng)Ad Hoc網(wǎng)絡(luò)基于位置的組播路由協(xié)議摘要：本文提出的是移動(dòng)Ad Hoc網(wǎng)絡(luò)基于位置的組播路由協(xié)議。一個(gè)網(wǎng)絡(luò)根據(jù)地理位置信息分為網(wǎng)格，這些網(wǎng)格網(wǎng)絡(luò)根據(jù)標(biāo)簽分為高通道子網(wǎng)和低頻道子網(wǎng)，根據(jù)源節(jié)點(diǎn)把目的節(jié)點(diǎn)分為子集。然后目的地節(jié)點(diǎn)分割成使用位置信息的組，這種組播路由就是沒一個(gè)標(biāo)簽組。擬議的議定書并不需要維持一個(gè)分布結(jié)構(gòu)（例如，樹狀或網(wǎng)格）。一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)只需使用關(guān)于其目的地和其鄰居的位置信息便能決定下一次跳轉(zhuǎn)的數(shù)據(jù)包轉(zhuǎn)交，因此非常適合高度動(dòng)態(tài)的網(wǎng)絡(luò)。提出的協(xié)議具有可擴(kuò)展性。1、前言移動(dòng)Ad Hoc網(wǎng)絡(luò)（ MANET網(wǎng)絡(luò)）是自組、動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)所形成的集合移動(dòng)節(jié)點(diǎn)通過無線鏈路。許多應(yīng)用中的移動(dòng)ad

2、hoc網(wǎng)絡(luò)依賴組通信。通信救災(zāi)期間、網(wǎng)絡(luò)游戲和車輛緊急警報(bào)網(wǎng)絡(luò)都是這些應(yīng)用程序常見的例子。因此，在移動(dòng)通信Ad hoc網(wǎng)絡(luò)中組播起著重要作用，并且這些年收到了極大地關(guān)注。一些組播協(xié)議的Ad Hoc網(wǎng)絡(luò)已經(jīng)提出，其中大多數(shù)是保持某種形式的分配結(jié)構(gòu)以提供組播。它們大致可分為樹為基礎(chǔ)的協(xié)議和網(wǎng)格為基礎(chǔ)的協(xié)議。樹為基礎(chǔ)的協(xié)議，比如AMRoute、MZR、ADMR和DRMR，只提供一個(gè)路徑之間對(duì)源和接收器。合并的道路，形成了所有接收組播樹。以網(wǎng)格為基礎(chǔ)的方法，可能有多個(gè)路徑之間發(fā)送和接收。這冗余提供更多的保護(hù)對(duì)拓?fù)渥兓?。例如網(wǎng)格為基礎(chǔ)的組播路由協(xié)議的移動(dòng)Ad Hoc網(wǎng)絡(luò)。基于位置的多播路由協(xié)議的移動(dòng)Ad

3、 Hoc網(wǎng)絡(luò)是DCMP、CAMP、NSMP和ODMRP。性能比較研究表明，樹為基礎(chǔ)的協(xié)議降低數(shù)據(jù)包投遞率和更糟的綜合性能優(yōu)于網(wǎng)格為基礎(chǔ)的移動(dòng)環(huán)境。當(dāng)一個(gè)多播組成員居住在一個(gè)特定領(lǐng)域時(shí)，了解地域位置的節(jié)點(diǎn)已用于改善ODMRP與移動(dòng)預(yù)測(cè)和限制洪水。在動(dòng)態(tài)源組播(DSM)，每個(gè)提供淹沒網(wǎng)絡(luò)的節(jié)點(diǎn)都提供自己的位置，因此每個(gè)節(jié)點(diǎn)都知道在Ad hoc網(wǎng)絡(luò)中其他節(jié)點(diǎn)的位置。發(fā)送一個(gè)多播包然后通過所有接受器的位置信息構(gòu)造一個(gè)組播樹。此樹一個(gè)封包的有效編碼。基于組播的位置(PBM)是推廣現(xiàn)有的單播路由算法。使用地理位置參與節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)包。關(guān)鍵是利用PBM規(guī)則分裂的多播數(shù)據(jù)包，和維修策略的情況下不存在任何直接的

4、鄰居，也是的取得一個(gè)或多個(gè)目的地的進(jìn)展。PBM只包括多播數(shù)據(jù)包標(biāo)題中所有目的地的地址，它沒有戰(zhàn)略的組織所有目的地并且選擇鄰居不僅取決于距離，可擴(kuò)展性仍然開放問題。可擴(kuò)展的組播被提議。本文主要是介紹組播協(xié)議的被提議的，網(wǎng)絡(luò)分為網(wǎng)格，采用擬議的議定書的位置信息進(jìn)行分類的目的地設(shè)定，并在每個(gè)網(wǎng)格選擇一個(gè)主機(jī)。這種網(wǎng)絡(luò)結(jié)構(gòu)成功地用于目的地節(jié)點(diǎn)集的整理，并直接傳送多播數(shù)據(jù)包。本文安排如下。第2節(jié)介紹了計(jì)劃的建構(gòu)性和標(biāo)簽分配的二維網(wǎng)格；第3節(jié)給出了位置為基礎(chǔ)的單播路由協(xié)議；第4節(jié)中，我們提出了多播路由協(xié)議；第5節(jié)為結(jié)論，并提出了進(jìn)一步的工作。2、二維網(wǎng)格的建設(shè)和標(biāo)簽分配假定每個(gè)節(jié)點(diǎn)了解自己的實(shí)際位置，也就

5、是其精確的地理坐標(biāo)，這可通過使用全球定位系統(tǒng)（ GPS ）和當(dāng)時(shí)的節(jié)點(diǎn)，收到自己的位置。它將其位置信息發(fā)送到所有其他節(jié)點(diǎn)。位置服務(wù)技術(shù)將被作為一個(gè)特殊的論文來討論。如圖1所示，MANET中的地理區(qū)域被分割成二維邏輯網(wǎng)格顯示。1 ，每個(gè)平方米被稱為一個(gè)網(wǎng)格區(qū)，每個(gè)網(wǎng)格是一個(gè)d × d正方形的大小，期中d是網(wǎng)格的邊長(zhǎng)設(shè)R是傳播的無線電信號(hào)，對(duì)于d來說更小的值意味著網(wǎng)絡(luò)中更多的網(wǎng)關(guān)，而這又意味著更高的費(fèi)用提供更多的數(shù)據(jù)包和廣播風(fēng)暴。如果d太大，無線電信號(hào)網(wǎng)關(guān)主機(jī)將難以達(dá)到網(wǎng)格以外的的地方，從而網(wǎng)關(guān)到網(wǎng)關(guān)的通信是不可能取得成功。d的值涉及到r和路由協(xié)議。本文圖2我們確定d和r的關(guān)系為。2，保

6、證一個(gè)主機(jī)已達(dá)到任何相鄰的東八區(qū)主機(jī)。這是方便的選擇在一個(gè)網(wǎng)格的網(wǎng)關(guān)。圖1，邏輯網(wǎng)格劃分物理領(lǐng)域圖2，無線電信號(hào)一個(gè)網(wǎng)格r和邊長(zhǎng)d的傳播關(guān)系在本節(jié)中，我們將提出一個(gè)標(biāo)簽任務(wù)計(jì)劃的網(wǎng)格拓?fù)洌⒆C明該任務(wù)計(jì)劃將提供單播路由網(wǎng)格中來源和目的節(jié)點(diǎn)間跳躍的最短路徑。假設(shè)一個(gè)在二維網(wǎng)格中地址為整數(shù)坐標(biāo)為（x，y），左下角為（0，0）。每個(gè)網(wǎng)格分配一個(gè)為l（u）的標(biāo)簽。標(biāo)簽賦值函數(shù)l表示為一個(gè)m×n的網(wǎng)格區(qū)域。x，y坐標(biāo)網(wǎng)格如下：y是偶數(shù)y是奇數(shù)在圖1中的每個(gè)邏輯網(wǎng)格都標(biāo)有一個(gè)l(u)的標(biāo)簽。圖3展示了一個(gè)6×5的網(wǎng)格區(qū)域，在每個(gè)網(wǎng)格所代表的一個(gè)整數(shù)，我們可以認(rèn)為每一個(gè)網(wǎng)格可以與八個(gè)鄰居

7、直接連接，標(biāo)簽有效地把一個(gè)網(wǎng)格網(wǎng)絡(luò)分成兩個(gè)子網(wǎng)。高通道子網(wǎng)被用于溝通低標(biāo)網(wǎng)（網(wǎng)關(guān)）到高標(biāo)網(wǎng)（網(wǎng)關(guān)），例子如圖4（a）；地通道子網(wǎng)絡(luò)可以用作在高標(biāo)網(wǎng)（網(wǎng)關(guān)） 到低標(biāo)網(wǎng)（網(wǎng)關(guān)）的傳輸，如圖4（b）。組播通信將使用郵件路由的標(biāo)簽。如果標(biāo)簽的目的地區(qū)大于其源區(qū)標(biāo)簽，組播路由總是發(fā)生在高通道子網(wǎng)，否則，它將采取低頻道子網(wǎng)。圖3，6 × 5網(wǎng)格網(wǎng)絡(luò)的標(biāo)簽（a）高通道子網(wǎng) （b）低通道子網(wǎng)圖4，在6 × 5網(wǎng)格網(wǎng)絡(luò)中的高頻道和低頻道子網(wǎng)3、單播路由協(xié)議設(shè)計(jì)一個(gè)路由協(xié)議應(yīng)考慮三個(gè)主要問題：路由發(fā)現(xiàn)、分組中繼和路由維護(hù)。在路由發(fā)現(xiàn)中，位置信息用來確定路由的質(zhì)量。Ad Hoc網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)從

8、一個(gè)系統(tǒng)如全球定位系統(tǒng)（GPS）中獲得其位置。在位置不知道的協(xié)議中，路由發(fā)現(xiàn)由盲目的泛洪式搜索完成，這很容易導(dǎo)致廣播風(fēng)暴問題。7中基于位置的組播方案用轉(zhuǎn)發(fā)區(qū)域來避免網(wǎng)絡(luò)范圍的泛式搜索，因?yàn)樗霓D(zhuǎn)發(fā)區(qū)域太廣，在一個(gè)轉(zhuǎn)發(fā)區(qū)域內(nèi)可能存在大量不必要的泛式搜索數(shù)據(jù)包，且當(dāng)一個(gè)數(shù)據(jù)源達(dá)不到它的目的地時(shí)，它無法給出如何選擇中繼主機(jī)的方案。本文將解決這個(gè)問題。我們假設(shè)一個(gè)數(shù)據(jù)節(jié)點(diǎn)知道它全部目的地的位置。定位服務(wù)我們將在另一片文章中進(jìn)行特殊的討論。一個(gè)數(shù)據(jù)節(jié)點(diǎn)將一個(gè)數(shù)據(jù)包傳向一個(gè)鄰近的節(jié)點(diǎn)，此節(jié)點(diǎn)靠近其目的節(jié)點(diǎn)。一個(gè)數(shù)據(jù)源的位置及其目的地被用來限制轉(zhuǎn)發(fā)范圍。當(dāng)達(dá)到一個(gè)目的節(jié)點(diǎn)時(shí)，一個(gè)相同的過程將會(huì)重復(fù)進(jìn)行。在單

9、一路由協(xié)議中，路由通過網(wǎng)格網(wǎng)關(guān)用網(wǎng)格到網(wǎng)格的方式運(yùn)行。如果一個(gè)網(wǎng)關(guān)脫離原來的網(wǎng)格，一種類似于蜂窩系統(tǒng)中的“越區(qū)切換”程序的行為將會(huì)發(fā)生。在這種情況下，一個(gè)網(wǎng)關(guān)將其路由信息傳送到下一個(gè)網(wǎng)關(guān)。每個(gè)網(wǎng)關(guān)在它的網(wǎng)格區(qū)域保持了其節(jié)點(diǎn)信息，且有一個(gè)規(guī)則來決定節(jié)點(diǎn)將傳送數(shù)據(jù)到哪個(gè)網(wǎng)格。只有本地信息，而非全球性的信息，用來轉(zhuǎn)發(fā)數(shù)據(jù)包。在我們的協(xié)議設(shè)計(jì)中，我們將考慮兩個(gè)問題，一個(gè)是在信息路由的每個(gè)步驟中盡可能少的節(jié)點(diǎn)被搜索到，另一個(gè)是路由路徑竟可能短。我們假定每個(gè)數(shù)據(jù)源節(jié)點(diǎn)能夠通過定位服務(wù)機(jī)制得到其目的地的位置。因此，到轉(zhuǎn)換區(qū)域的一個(gè)路線可以由發(fā)送端的位置和目的地的坐標(biāo)來確定。我們將兩個(gè)網(wǎng)格間的距離定義為：，

10、。通過當(dāng)前網(wǎng)格的鄰居網(wǎng)格與目的節(jié)點(diǎn)所在的網(wǎng)格之間的距離來選取一個(gè)轉(zhuǎn)換轉(zhuǎn)換網(wǎng)格，然后選擇與目的網(wǎng)格距離最短的網(wǎng)格作為一個(gè)轉(zhuǎn)換網(wǎng)格。令V是一個(gè)網(wǎng)絡(luò)中所有網(wǎng)格的集合。尋找一個(gè)2D網(wǎng)格的無死鎖的單播算法就是定義一個(gè)路由函數(shù)：，在這種方式中它運(yùn)用了兩個(gè)子網(wǎng)來避免循環(huán)路由。這里，兩個(gè)網(wǎng)格和是相鄰的，例如， 。有一個(gè)這樣的路由函數(shù)：一個(gè)數(shù)據(jù)源節(jié)點(diǎn)在網(wǎng)格，目的節(jié)點(diǎn)在網(wǎng)格，定義，則是的一個(gè)鄰近網(wǎng)格，且如果，我們有如下等式：，否則，如果，我們有如下等式：。如果有更多的主機(jī)滿足條件，我們只有全部選取。（a）數(shù)據(jù)源1，目的地28 （b）數(shù)據(jù)源23，目的地6圖5：在網(wǎng)格的高通道和低通道子網(wǎng)中的單播路由單播通信用標(biāo)簽作為

11、路由。圖5展示了高通道子網(wǎng)和低通道子網(wǎng)中的單播路由。圖5（a）給出了在高通道子網(wǎng)中從網(wǎng)格s（）的一個(gè)數(shù)據(jù)源主機(jī)到網(wǎng)格d（）的目的主機(jī)的所有可能路線，其中所有的路線都只是從低標(biāo)簽網(wǎng)格的主機(jī)到高標(biāo)簽網(wǎng)格的主機(jī)；圖5（b）給出了在低通道子網(wǎng)中從網(wǎng)格s（）的一個(gè)數(shù)據(jù)源主機(jī)到網(wǎng)格d（）的目的主機(jī)的所有可能路線，其中所有的路線都只是從高標(biāo)簽網(wǎng)格的主機(jī)到低標(biāo)簽網(wǎng)格的主機(jī)。在每步中數(shù)據(jù)包將一個(gè)中繼點(diǎn)轉(zhuǎn)發(fā)到最接近其目的地的位置，在網(wǎng)格水平上數(shù)據(jù)源與其目的地間的路線遵循最短路徑。4、組播路由協(xié)議對(duì)于從源節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)集D的組播路由，其算法有兩部分組成：信息編制和路由。第一部分將一個(gè)信息的目標(biāo)集合在兩步中分為多個(gè)

12、子集。第一步，節(jié)點(diǎn)S生成的信息的目標(biāo)集合被分為兩個(gè)子集和，包含所有目標(biāo)節(jié)點(diǎn)網(wǎng)格高于網(wǎng)格S的值，包含所有目標(biāo)節(jié)點(diǎn)低于網(wǎng)格S的值。運(yùn)用它們的網(wǎng)格標(biāo)簽作為一個(gè)關(guān)鍵點(diǎn)，將中的目標(biāo)節(jié)點(diǎn)按遞增次序分類。對(duì)也做同樣的處理，但按照遞減的次序。第二步，目標(biāo)集合和被分別分為更多的組，這些組取決于和相應(yīng)目標(biāo)節(jié)點(diǎn)間的網(wǎng)格的距離。第二部分決定了信息的路徑直至每組的所有目標(biāo)節(jié)點(diǎn)都達(dá)到。路由通過運(yùn)用單播路由協(xié)議每組中標(biāo)簽的順序來完成。為了敘述的簡(jiǎn)潔明了，其中的網(wǎng)格和節(jié)點(diǎn)用同一標(biāo)簽標(biāo)示，兩個(gè)節(jié)點(diǎn)間的距離意味著兩個(gè)節(jié)點(diǎn)分別所在的網(wǎng)格間的距離。算法1。組播路由從S到目的地設(shè)定為DH（或DL）1，讓節(jié)點(diǎn)為dn,n=1,2,.為DH

13、的第n個(gè)節(jié)點(diǎn)，并以升序排列（或在DL中以降序排列）。如果d(d1,d2)>d(S,d2)，那么d1，d2在不同的組，否則d1，d2在同一組。2，假設(shè)在DH（或DL）的前n節(jié)點(diǎn)已被分成不同的組Gi，1ik，并讓gi節(jié)點(diǎn)為Gi的最大序列號(hào)（或最小序列號(hào)），如果d（dn+1，gi）>d（dn+1，S），其中1ik，則dn+1在新組且k+1=>k，否則dn+1屬于，d(dn+1,gm)=mind(dn+1,gi)|1ik且n+1=>n。3，如果n<|DH|(or n<|DL|)，參考24，S 以單播路由算法發(fā)往Gi第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)包，1ik5，對(duì)于每個(gè)平行的Gi，讓

14、|Gi|=ki,gjGi,1jki對(duì)于j=1到用單播路由算法發(fā)送數(shù)據(jù)包從到在這里，我們將討論算法1的時(shí)間復(fù)雜度，我們把|DH|設(shè)為目的節(jié)點(diǎn)，在第1步，我們需要時(shí)間常數(shù)O(1)；第2步復(fù)雜時(shí)間為k，這里的k為租的數(shù)量且k|DH|。第2步和第3步會(huì)重復(fù)DH時(shí)間最多次。所以|DH|=n1，第2步復(fù)雜的時(shí)間和第3步算法1中。時(shí)間復(fù)雜度的排序DH是總時(shí)間復(fù)雜度的部分目的地節(jié)點(diǎn)DH為。在第4，5步中任何單播路由間的跳躍為不超過直徑為d的網(wǎng)絡(luò)，所以第4，5步中時(shí)間復(fù)雜度為O(dn1)。算法1中總時(shí)間復(fù)雜度到目的地DH為O(n1(d+n1)。如果|DL|=n2，則算法1中的總時(shí)間復(fù)雜度到DL為O(n2(d+n

15、2)。提出的組播路由算法的性能取決于目標(biāo)節(jié)點(diǎn)的位置分布。為了減少2D網(wǎng)格中的時(shí)間成本，終端集合和可被進(jìn)一步分塊。集合可被分為兩個(gè)集合，一個(gè)集合包含了坐標(biāo)大于或等于源節(jié)點(diǎn)S坐標(biāo)的所有節(jié)點(diǎn)，另一個(gè)集合則包含了剩余的節(jié)點(diǎn)。采用相同的方法來劃分。算法1被同時(shí)用于四個(gè)子集，時(shí)間的復(fù)雜程度則可以降低。目的地節(jié)點(diǎn)升序排列，并為目的地的每組設(shè)置DH，降序排列每組設(shè)定DL，郵件路由使用每組中每一對(duì)連續(xù)的目的地節(jié)點(diǎn)的單播協(xié)議。組播路由路徑圖如圖7所示 源節(jié)點(diǎn)的網(wǎng)格目的節(jié)點(diǎn)的網(wǎng)格圖6。把分區(qū)目的地劃分為6×5網(wǎng)格不同組的例子源節(jié)點(diǎn)的網(wǎng)格目的節(jié)點(diǎn)的網(wǎng)格圖7.多播路由作為6×5網(wǎng)格的不同組5、結(jié)論在本文中，我們對(duì)移動(dòng)ad hoc網(wǎng)絡(luò)提出了一種組播路由模式。新的路由方案基于主機(jī)的地理位置信息，首先，一個(gè)