一種適合無線網狀網機會性路由的路由量度方法
2023-06-01 11:23:31
專利名稱：一種適合無線網狀網機會性路由的路由量度方法
技術領域：
本發明涉及無線網絡路由領域，特別是涉及無線mesh網絡機會性路由的路由量度。
背景技術：
無線網狀網絡(WirelessMeshNetwork，麗N)也稱為多跳(multi-hop)網絡，其核心指導思想是讓無線網絡中的每個節點都可以發送和接收信號。在無線網狀網絡中，任何無線設備節點都可以同時作為AP (AccessingPoint)和路由器，每個節點都可以與一個或者多個對等節點進行直接通信。這種結構的最大好處在於如果最近的AP由於流量過大而導致擁塞的話，那麼數據可以自動重新路由到一個通信流量較小的鄰近節點進行傳輸。依此類推，數據包還可以根據網絡的情況，繼續路由到與之最近的下一個節點進行傳輸，直到到達最終目的地為止，這樣的訪問方式就是多跳訪問。多跳訪問方式使普通無線技術過去一直存在的可擴充能力低和傳輸可靠性差等問題迎刃而解。網絡中大量終端設備能自動通過無線連成網狀結構，網絡中的每個節點都具備自動路由功能，每個節點只和鄰近節點進行通信，因此是一種自組織、自管理的智能網絡，不需主幹網即可構築富有彈性的網絡。
路由量度(RoutingMetric)是一組參數，通過它們一個路由選擇公式決定一個更優的路由。每一種路由量度均從不同角度衡量了某種鏈路代價開銷。當進行路由發現或路由維護時，均首先從路由表中判斷鄰居節點的路由量度值的大小，然後再選擇下一跳轉發節點。目前典型的路由量度方法有以下幾種跳數量度(hopco皿t， Hops), Hops量度方法選擇總跳數最小的路徑作為數據傳輸路徑。單跳選路時，鏈路質量的量度呈現出二進位特性，鏈路或者存在，或者不存在。 單g兆往返時間量度(perhoproundtriptime， Per-RTT) ， Per-RTT量度方法是通過在相鄰節點之間發送探測包，以此來測量探測包的往返時延，路由算法選擇單跳往返時間最小的路徑進行傳輸。 期望的發包數(expectedtransmissioncount， ETX) ， ETX量度方法是發送節點通過定期發送廣播包測得其與鄰居節點之間正向及反向鏈路的包接受率，從而估計出要正確傳輸一個數據包所需重發的包的數量。路由算法選擇期望發包次數較小的鄰居節點作為下一跳。 上述幾種路由量度方法的思想均是基於傳統路由方式，而忽略了無線網絡機會性路由本身的特性。機會性路由，是指在數據包傳輸完成後再確定哪些接收到數據的節點成為路由的下一跳。在無線網狀網絡中，傳輸信道是無線的，數據傳輸的本質是廣播，因此，處於該次傳輸的發送節點和接受節點附近的其他節點都可以機會性地接收到此次傳輸的數據。對於傳統的路由方式，無線信道的廣播性使其在選路過程中產生了許多冗餘鏈路，佔用了大量網絡資源，而機會性路由則是從充分利用這些冗餘鏈路的角度出發，在節點將數據
4發送出去之後，讓收到數據的節點都參與數據的轉發，並根據各節點的機會性接收情況來選擇合適的節點成為傳輸的下一跳。因此，機會性路由勢必會對無線網狀網絡的數據傳輸性能帶來較大提高。
發明內容
本發明針對現有技術所存在的缺陷和不足，其目的在於提供一種更加適用於無線網狀網機會性路由的路由量度方法，採用該路由量度方法確定數據傳輸路由，減少節點間的數據傳輸次數，提高網絡的吞吐率。 本發明以節點間機會性轉發時成功傳輸一個包所需要的最少傳輸次數ELT(ExpectedLeastTransmissions期望最少傳輸次數)作為機會性路由量度，並基於此路由量度定義節點間距離，劃分上遊節點和下遊節點。本發明包括如下步驟
第一步，對每個無線Mesh節點加載一個探測包隊列，並按照一定的時間間隔周期性發送探測包，同時接受其他節點發送的探測包，將所接收到探測包的發送點標記為接受節點的鄰居節點，並通過檢測一段時間內收到鄰居節點的探測包個數計算出節點間的前向包和反向包發送成功率。對無線任意一條鏈路A—B，節點A周期性地(周期設為(1+Y)秒，Y為(0，0. 1)之間的一個隨機數，稱為震蕩時間)發送探測包給B。在B節點處設置一個長度為s的窗口 ，記錄在過去的s秒內B成功接收到來自A節點探測包的次數c，並用c/s作為A—B鏈路前向包成功發送率。反之B節點周期性地發送探測包給A，同理可以求出A—B鏈路的反向包成功發送率。 所述前向包發送成功率是指某鄰居節點接受到本地節點發送的包的概率。 所述反向包發送成功率是指本地接受到某鄰居節點發送的包的概率。 第二步，根據第一步中所得的鏈路前向和反向包成功發送率，計算得到各節點對
其所有相鄰節點的發包成功率統計表，作為路由量度的初始依據。 所述發包成功率是指目的節點成功收到來自源節點的數據包，且源節點成功接收到來自目的節點的ACK包的概率，所以發包成功率p等於前向包成功發送率pf與反向包成功發送率pr的乘積，即。 第三步，根據第二步中生成的發包成功率統計表，計算得到各節點到其所有相鄰節點的單跳鏈路ETX統計表。 所述ETX是指節點間沿最短路徑成功傳送一個探測包所需傳輸次數的預測值。不妨設本地節點到某一相鄰節點的發包成功率為P，那麼單跳鏈路的ETX的公式為
第四步，根據第三步中生成的單跳鏈路ETX統計表，計算出各節點到目的節點的ETX值，即到目的節點的鏈路中各段單跳鏈路ETX之和的最小值，並將這些節點到目的節點的ETX升序排列，以此區分上、下遊節點和距離的遠近。按升序排序後的目的節點的序號為1，源節點的序號為n，則中間節點為2，3，4……n-l。那麼源節點的下遊節點集為{1，2，3 n-lh這裡將節點集{1，2，3 n-l}簡記為{n_l}。 所述上、下遊節點是相對於傳輸過程中的目的節點而言的，用各節點到目的節點的距離來區分，距離小的是下遊節點，距離大的是上遊節點。 所述到目的節點的距離依賴於採用的路由量度，不同的路由量度定義的距離是不同的。
第五步，根據第四步中得出的節點上下遊關係，計算出本地節點需要發送包的次 數，設為，以使得至少一個下遊節點能夠收到其發送的包。對於某節點s，其下遊節點集為 {1， 2……s-1}，先計算節點s的下遊節點集中至少有一個節點收到包的概率，記為，簡記為。 則有，表示節點s到下遊節點i之間的發包成功率。當節點集只有一個節點i時，；然後計 算，得到節點s成功傳輸一個數據包到下遊節點集所需要的最少傳輸次數。
第六步，根據第四步中得出的節點上下遊關係，計算出本地節點的下遊節點集中 至少有一個節點收到包的情況下，數據包從收到包的下遊節點發送到目的節點需要的轉發 次數。先計算節點s的下遊節點k收到包的概率，，對於目的節點，即節點序號k=l時，等於 節點s到目的節點的數據包成功接收率，即；對於其他節點，即節點序號大於1而小於s的 節點，，因此；然後計算讓下遊節點集中每個節點都參與傳輸時所需的總傳輸次數，該值採 用遞歸迭代算法，按照節點序號先計算出前面節點的ELT值，利用這些ELT值來計算；最後 得到從下遊節點集成功傳輸到目的節點所需要的最少傳輸次數。 第七步，將第五步和第六步的結果相加，，得到本地節點的ELT值，即本地節點到 目的節點的期望最少傳輸次數，然後按各節點的ELT升序排列，以此確定最終的上、下遊節 點關係。 與現有技術相比，本發明具有如下的有益效果
1.提出一種適合無線網狀網絡中機會性路由的路由量度ELT，以源節點和目的節 點間機會性轉發時成功傳輸一個包所需要的最少傳輸次數為定義節點間距離的路由判據， 充分考慮了無線鏈路存在的幹擾及負載情況、以及無線網絡數據傳輸的廣播特性，因此與 Hops、ETX等傳統路由量度相比，減少了節點間的數據傳輸次數，從而提高了網絡的吞吐率。
2.基於ELT定義節點間距離，劃分上遊節點和下遊節點，選擇出適合無線網狀網 機會性路由的最優轉發節點集，充分利用網絡中空閒節點的傳輸能力來發揮機會性路由的 優勢，讓網絡中收到數據包的節點都參與轉發，因此與Hops、ETX等傳統路由量度相比更加 適合於機會性路由中機會性轉發節點集的選擇。
下面結合附圖和具體實施方式
對本發明的技術方案作進一步具體說明。
圖1為本發明的流程圖。
圖2為本發明實施例的節點布置關係拓撲圖。
具體實施例方式
下面結合圖1、2對本發明的實施例作詳細說明本實施例在以本發明技術方案為 前提下進行實施，給出了詳細的實施方式和具體的操作過程，但本發明的保護範圍不限於 下述的實施例。 本實施例以一個4層的教學樓為例，如圖2所示，節點布置在房間中， 一樓和四樓 均有一個房間布置了節點，分別為105室和410室，二樓和三樓均有兩個房間布置了節點， 分別為205室、210室和310室、315室。 當前105室的某PC機想發送數據給410室，其步驟如下
第一步，對每個無線Mesh節點加載一個探測包隊列，並按照一定的時間間隔周期性發送探測包，同時接受其他節點發送的探測包，將所接收到探測包的發送點標記 為接受節點的鄰居節點，並通過檢測一段時間內收到鄰居節點的探測包個數計算出節點間 的前向包和反向包發送成功率。本實施例中作為檢驗節點的'210'(其他節點行為與其相 同)在第一步過程中發現'105'， '310'， '315'和'410'，並可以計算與之相鄰節點的前向 包發送成功率和反向包發送成功率。 第二步，根據第一步中所得的鏈路前向和反向包成功發送率，計算得到各節點對 其所有相鄰節點的發包成功率統計表，作為路由量度的初始依據。本實施例中'210'根據 與其鄰居節點'105'， '310'， '315'禾P'410'的前向包發送成功率和反向包發送成功率計算 出與他們之間的發包成功率，並記錄為發包成功率表，如'210'到'315'的前向包發送成功 率為0. 6，反向包發送成功率為0. 5，則他們之間的發包成功率為0. 6*0. 5=0. 3。
第三步，根據第二步中生成的發包成功率統計表，計算得到各節點到其所有相鄰 節點的單跳鏈路ETX統計表。本實施例中，'210'到其鄰居節點'105'， '310'， '315'和 '410'的單跳鏈路ETX表可以通過公式求得，如'210'到'315'的單跳。
第四步，根據第三步中生成的單跳鏈路ETX統計表，計算出各節點到目的節點的 ETX值，並將這些節點按到目的節點的ETX升序排列，以此區分上、下遊節點和距離的遠近， ETX值越小表示距離目的節點越近。本實施例中，'210'到目的節點'410'的鏈路中，各鏈 路的ETX值之和如下
210—310—410 :
210—410 :
210—315—410 :
其他鏈路的ETX顯然會更大，因此就不一一列出了。通過比較，鏈路'210' — '415' 的ETX=2. 5為最小，因此'210'節點到目的節點'415'的ETX記為2. 5。
同樣，可得出其他節點的ETX :
節點 105205210310315410
ETX 4. 17 3. 33 2. 50 1. 25 2.00 0
按其升序排序為:{410， 310， 315， 210， 205， 105}。
第五步，根據第四步中得出的節點上下遊關係，計算出本地節點需要發送包的次 數，以使得至少一個下遊節點能夠收到其發送的包。本實施例中，'210'節點的下遊節點集 為{410，310，315}，根據可知該節點集接收到'210'發送的包的概率為，所以'210'節點成 功傳輸一個數據包到下遊節點集所需最少傳輸次數為。 第六步，根據第四步中得出的節點上下遊關係，計算出本地節點的下遊節點集中 至少有一個節點收到包的情況下，數據包從收到包的下遊節點發送到目的節點需要的轉發 次數。本實施例中，以'210'節點作為源節點發送數據包，下遊節點集{410，310，315}中節 點k收到數據包的概率，那麼有
q f ELT 4跳4 0. 4 0
3100.88 0.48 1.25
3150.916 0.036 2
所以，得到從下遊節點集成功傳輸到目的節點所需要的最少傳輸次數。
7
第七步，將第五步和第六步的結果相加，即得到本地節點的ELT值，即本地節點到 目的節點的期望最少傳輸次數，並按各節點的ELT升序排列，以此確定節點間的最終上下 遊關係。本實施例中，'210'節點的ELT值為1. 09+0. 73=1. 82。同樣，得到其他節點的ELT 值
節點 410310315210205105
ELTO 1. 25 2. 00 1. 82 3. 33 3. 16
按ELT升序排序為{410，310，210，315，105，205}，作為最終的上、下遊節點關係。由此 可知，在本實施例中，源節點'105'發送數據後，'205'節點和'315'節點參與機會性轉發， 當'210'節點收到數據包後選擇新的轉發節點'310'節點和'315'節點參與機會性轉發。 因此在此例中，以ELT為路由量度選擇的轉發節點集是適合機會性路由的轉發節點集。
最後所應說明的是，以上具體實施方式
僅用以說明本發明的技術方案而非限制， 儘管參照較佳實施例對本發明進行了詳細說明，本領域的普通技術人員應當理解，可以對 本發明的技術方案進行修改或者等同替換，而不脫離本發明技術方案的精神和範圍，其均 應涵蓋在本發明的權利要求範圍當中。
權利要求
一種適合無線網狀網機會性路由的路由量度方法，其特徵在於，它以節點間機會性轉發時成功傳輸一個包所需要的最少傳輸次數ELT作為機會性路由量度，包括如下步驟第一步，對每個無線Mesh節點加載一個探測包隊列，並按照一定的時間間隔周期性發送探測包，同時接受其他節點發送的探測包，將所接收到探測包的發送點標記為接受節點的鄰居節點，並通過檢測一段時間內收到鄰居節點的探測包個數計算出節點間的前向包和反向包發送成功率；第二步，根據第一步中所得的鏈路前向和反向包成功發送率，計算得到各節點對其所有相鄰節點的發包成功率統計表，作為路由量度的初始依據；第三步，根據第二步中生成的發包成功率統計表，計算得到各節點到其所有相鄰節點的單跳鏈路ETX統計表，所述ETX是指節點間沿最短路徑成功傳送一個探測包所需傳輸次數的預測值； 第四步，根據第三步中生成的單跳鏈路ETX統計表，計算出各節點到目的節點的ETX值，並將這些節點按到目的節點的ETX升序排列，以此區分上、下遊節點和距離的遠近，ETX值越小表示距離目的節點越近；第五步，根據第四步中得出的節點上下遊關係，計算出本地節點需要發送包的次數，以使得至少一個下遊節點能夠收到其發送的包；第六步，根據第四步中得出的節點上下遊關係，計算出本地節點的下遊節點集中至少有一個節點收到包的情況下，數據包從收到包的下遊節點發送到目的節點需要的轉發次數；第七步，將第五步和第六步的結果相加，即得到本地節點的ELT值，即本地節點到目的節點的期望最少傳輸次數，並按各節點的ELT升序排列，以此確定節點間的最終上下遊關係。
2. 根據權利要求1所述的適合無線網狀網機會性路由的路由量度方法，其特徵是，第二步所述發包成功率是指目的節點成功收到來自源節點的數據包，且源節點成功接收到來自目的節點的ACK包的概率，所以發包成功率p等於前向包成功發送率pf與反向包成功發送率pr的乘積，即J =
3. 根據權利要求2所述的適合無線網狀網機會性路由的路由量度方法，其特徵是，在第三步中計算單跳鏈路的ETX的公式為formula see original document page 2式中，p為本地節點到某一相鄰節點的發包成功率。
4. 根據權利要求3所述的適合無線網狀網機會性路由的路由量度方法，其特徵是，第五步中，對於某節點s，其下遊節點集為{1，2……s-lh節點s的下遊節點集中至少有一個節點收到包的概率，記為。
，簡記為，，％_1}=i-n(1-a),表示節點s到下遊節點i之間的發包成功率；節點s成功傳輸一個數據包到下遊節點集所需要的最少傳輸次數 - 1胸=——。
5. 根據權利要求4所述的適合無線網狀網機會性路由的路由量度方法，其特徵是，第六步中，出本地節點的下遊節點集中至少有一個節點收到包的情況下，數據包從收到包的下遊節點發送到目的節點需要的轉發次數的計算方法為先計算節點S的下遊節點k收到包的概率，對於目的節點，即節點序號k=l時，/(。等於節點S到目的節點的數據包成功接收率，即/化)=《W = A ;對於其他節點，即節點序號大於1而小於s的節點，xM 、 ，因此/(t) = 1 %} =， ， ^ ;然後計算讓下遊節點集中每個節點都參與傳輸時所需的總傳輸次數^-"^￡￡7(^，該值採用遞歸迭代算法，按照節點序號先充<3計算出前面節點的ELT值，利用這些ELT值來計算；最後得到從下遊節點集成功傳輸到目的三/(i)虹r(i)節點所需要的最少傳輸次數I^) = i1^_。
6.根據權利要求5所述的適合無線網狀網機會性路由的路由量度方法，其特徵是，所述第七步中，用公式虹r(s)z D(s)得到本地節點的ELT值。
全文摘要
本發明提出一種適合無線網狀網絡中機會性路由的路由量度方法，用於計算源節點和目的節點間機會性轉發時成功傳輸一個包所需要的最少傳輸次數，並基於此路由量度定義節點間距離，劃分上遊節點和下遊節點。該方法充分考慮了機會性路由的廣播特性，利用網絡中空閒節點的傳輸能力，讓網絡中收到數據包的節點都參與轉發，從而得到節點間按機會性路由方式轉發包時成功傳輸一個包所需要的最少傳輸次數。以最少傳輸次數為路由量度選出的轉發節點和傳統路由量度相比更加適應於機會性路由中機會性轉發節點集的選擇。
文檔編號H04L12/56GK101765143SQ201010125908
公開日2010年6月30日 申請日期2010年3月17日 優先權日2010年3月17日
發明者付逸斐, 華鵬, 石柯 申請人:華中科技大學