802.11多接口寬帶無線mesh網絡路由方法

2023-12-02 14:02:56

專利名稱：：802.11多接口寬帶無線mesh網絡路由方法
技術領域：
：本發明屬於寬帶無線mesh接入網
技術領域：
，特別涉及802.11多接口無線mesh網絡中的路由技術。
背景技術：
：近年來，一種新型的寬帶無線接入技術mesh網絡技術成為通信領域的一個重要話題，當前被廣泛議論的mesh網絡大多是採用802.11技術的多接口無線mesh網絡。路由技術是這種網絡的關鍵技術之一。路由的目的是為端到端數據流選擇最佳的路徑使得數據流在該路徑上傳輸可以達到的速率最高，而無線網絡的路由可以有表驅動和源路由兩種方式，如果採用表驅動，那麼無法為每個端到端數據流單獨選擇路徑，這樣端到端數據流通過表驅動獲得的路徑就無法保證是最佳的，因此無線網絡最好採用源路由，但是普通的源路由也有缺點源路由器需要為各數據包添加源路由路徑，從而增加包長，如果原始數據包長度已經為協議規定的最大包長，那麼必須為數據包進行分片，對那些不允許分片的數據包就只能丟棄，這就會導致某些端到端數據流無法進行傳輸。傳統的基於最小跳數的路由簡單而且快速，但是對於無線mesh網絡來說，路由器之間的無線鏈路的質量受環境影響很大、不穩定，而且鏈路兩端距離越大，鏈路的質量越差，速率就越低，特別是802.11g中規定了從lmbps到54mbps不等的速率，所以路徑的跳數越小就意味著路徑上各鏈路兩端的距離越大從而使得鏈路的速率可能很低，整個路徑的端到端速率就會因此變得很低，因此為了提高路徑端到端速率，不應該使用基於最小跳數的路由。目前學術界都研究基於鏈路質量的路由，但是目前學術界已經提出的各種基於鏈路質量的路由方法都需要通過多個參數來衡量鏈路質量，但是獲取這些參數需要很大的開銷，而且它們大多是物理層的一些參數，難於獲取並可能不被當前商用無線網卡的驅動所支持。
發明內容本發明所要解決的技術問題是提供一種簡單方便且能夠提高端到端速率的802.11多接口寬帶無線mesh網絡路由方法。所述的802.11多接口無線mesh網絡由多個無線路由器組成，這些路由器都有多個802.ll無線接口，可以分別使用三個正交信道，按照功能不同這些路由器可以分為三類1)普通路由器，這種路由器只用於路由數據包，其無線接口都使用ad-hoc模式，用於和周圍路由器進行無線互連；2)帶AP功能的路由器，這種路由器除了用於路由數據包，還用於為用戶提供寬帶接入，所以要有一個接口使用AP模式供用戶接入，其餘接口使用ad-hoc模式；3)網關路由器，這種路由器通過光纜或其他網絡連接設備接入有線骨幹網，為整個mesh網絡提供到有線骨幹網的寬帶數據接入，它們的無線接口也都使用ad-hoc模式；為了進行無線互連，使用相同信道且使用ad-hoc模式的無線接口使用同一個網段的IP。本發明的技術方案的總體結構是1)當路由器為數據包查找路由失敗，或者帶AP功能的路由器設定的到網關路由發現定時器的定時時間到，則進行路由發現；2)當路由器發現鏈路失效，則進行錯誤恢復。本發明的技術方案具體包括以下部分1)每個路由器預先分配一個固定的節點號(ID)，並維護一張IP與ID對應的列表，該列表稱為"IP—ID"列表；2)路由器基於源路由器ID和目的路由器ID為數據包進行路由查找；3)若路由査找失敗，或者帶AP功能的路由器設定的到網關路由發現定時器的定時時間到則基於源路由器ID和目的路由器ID進行路由發現；4)若發現鏈路失效，則基於源路由器ID和目的路由器ID進行錯誤恢復。由此本發明提供了一種簡單方便且能夠提高端到端速率的802.11多接口寬帶無線mesh網絡路由方法。本發明中，所說的"IP—ID"列表是預先為各路由器設置的一張列表，該表由一系列表項構成，除了一個默認的表項以外，其餘每個表項都表示一個IP位址或IP網段及與其對應的路由器ID;這裡，"對應"的意思是指該表項中的每個IP位址或網段由節點號為該表項中的ID的路由器管理。該列表中，默認的表項代表不屬於本mesh網絡的IP位址或IP網段對應的ID為0。由於國際標準規定240.0.0.0/8網段的IP位址不能被用來分配給任何網絡接口，這樣240.0.0.0對應的ID將肯定為O。本發明中，所說的路由器基於源、目的路由器ID為數據包進行路由查找的步驟為1)通過査找"IP—ID"表確定數據包源IP、目的IP對應的源路由器IDs_id、目的路由器IDd—id;2)如果d—id為本路由器ID,或者d—id為0且本路由器為網關路由器，那麼直接使用數據包目的IP查找路由表，否則使用240.0.目的路由器ID.源路由器ID，即240.0.d—id.s—id作為目的IP位址査找路由表。本發明中，所說的基於源路由器ID、目的路由器ID進行路由發現，目的是建立發起請求的路由器到目的路由器之間的正向和反向路徑，包括以下a)至d)四個步驟a)源路由器發起路由請求。在兩種情況下路由器會發起路由請求1)為某個數據包查找路由失敗，立即發起到目的地址的路由請求；2)網關路由請求定時器定時時間到，立即發起到網關的路由請求。其中網關路由請求定時器是帶AP功能的路由器設定的一個周期定時器，定時時長可以設為10min,設定該定時器的目的是周期性的主動發起到網關的路由請求。每次發起的路由請求都有一個唯一的路由請求標識{發起請求路由器ID(s_id)，目的路由器ID(d—id),序列號(sequence)}，表示由s—id路由器發起的到d—id路由器的第sequence個路由請求。每個路由器都把sequence值初始化為l，每發起一次請求後都要將該值加1。路由器一旦發起路由請求，需要在各ad-hoc接口上廣播路由請求(rreq)包。一個rreq包包括固定和可變兩個部分。發起請求的路由器發送的rreq包只包括固定部分，它包括1)type,其值設為l，代表該路由包是rreq包；2)length,代筆該包長度，單位是字節；3)sequence,表示該路由請求序列號；4)src_if—ip，代表發起路由請求的路由器發送該rreq包時用的接口的IP;5)src—if—load,代表IP為src—if—ip的接口的數據包流量；6)dst_ip，代表路由請求的目的地址，發起到網關的請求時將該地址設為240.0.0.0;7)hop,代表當前該rreq包被轉發的次數，發起請求的路由器需要將其設為0;8)rssi，代表該rreq包被接收時的RSSI值，發送rreq包的路由器並不為其賦值，其值留給收到該包的路由器在網卡驅動層賦值。可變部分由轉發rreq包的路由器添力口，一旦路由器在各接口上轉發rreq包，都需要在包尾添加以下內容l)rssi，填入包固定部分中rssi欄位的值；2)recv_if—ip，代表收到該rreq包的接口的IP;3)recv—if—load,代表IP為recv—if—ip的接口上的數據包流量；4)send_if—ip，代表路由器轉發該rreq包時用的接口的IP;5)send—if_load，代表IP為send_if_ip的接口上的數據包流量。除了在可變部分中添加內容，路由器轉發rreq包時還需要修改固定部分中length和hop的值length+=17(添加部分內容長度)、hop++。b)收到從不同路徑上轉發過來的路由請求(rreq包)的路由器處理該請求，路由器在處理該請求的過程中使用路徑比較函數來選擇最優路徑。每個rreq包都代表了一個路由請求，而且代表了一條路徑，即包含了從發起請求的路由器到收到該rreq包的路由器的路徑信息，路徑信息包括該路徑的跳數、路徑上各接口的IP及數據包流量、路徑中每條鏈路上接收該rreq包時的RSSI。根據這些信息可以計算l)路徑中每條鏈路上接收該rreq包的RSSI中的最小值RSSImin;2)路徑的信道差異指數CDI:其中N為路徑跳數，Nl，N2，N3分別為使用3個正交信道的鏈路數目；3)路徑的剩餘容量指數LRCI:式中，N為路徑跳數，V，V為路徑上第k條鏈路的兩個接口上的流量，單位為路由器收到別的路由器廣播的rreq包，先通過包中src—if_ip、dst_ip和sequence判斷該請求是否已經過期，方法為首先查找"IP—ID"列表，確定src—if_ip和dst—ip對應的ID:s_id、d_id;然後査找"路由請求列表"，找到源、目的ID分別為s—id、d一id對應的路由請求表項，如果rreq包中sequence的值小於査找到的路由請求表項的sequence的值，表示該請求已經過期。如果請求己經過期那麼路由器將不對該包進行處理，否則該請求沒有過期，那麼執行以下步驟l)如果d一id不為0，或者d一id為O但本路由器不是網關路由器，那麼執行步驟2)，否則執行步驟4);2)如果該請求是一個新的請求，那麼直接把該rreq包代表的路徑記為該請求對應的最優路徑，並執行步驟3)，否則使用路徑比較函數判斷該rreq包代表的路徑是否優於當前記錄的對應該請求的最優路徑，如果是則更新該最優路徑並執行步驟3)，否則丟棄該包並不再執行下面的步驟；3)如果d—id為本路由器ID，那麼路由器需要對該請求進行路由回復，否則在各接口上轉發rreq包。路由器不再執行下面的步驟。4)如果該請ZJC/=min{求是一個新的請求則記錄該rreq包的路徑信息並為該請求開啟一個時長為500ms的路由回復定時器，否則執行步驟5);5)如果該rreq包的收包時間已經超過了該rreq包對應的請求的定時時間則丟棄該包不進行處理，否則用路徑比較函數判斷該rreq包代表的路徑是否優於當前記錄的最優路徑，如果是則更新當前記錄的最優路徑信息。本發明所述的"路由請求列表"也由一些列表項構成，每一條表項都是一個路由請求標識{s—id，d—id，sequence},記錄由s—id路由器發起的d—id路由器的"最新"的路由請求，"最新"指的是該表項中sequence的值為路由器當前收到的由s一id發起的到d—id的rreq包中的sequence的最大值。本發明所述的綜合考慮跳數、RSSI、CDI、LRCI進行路徑選擇，關鍵在於採用的路徑比較函數，該函數用來根據兩條路徑上的跳數、RSSImin、CDI、LRCI，判斷兩條路徑的優劣，步驟為1)如果兩條路徑的跳數差大於1，那麼直接判定跳數小的路徑優否則執行步驟2;2)如果其中一條路徑的RSSImin或者兩條路徑上的RSSImin均小於一個預先設定的門限Y，而且兩條路徑的RSSImin的差值大於另一個預先設定的門限S，那麼直接判定RSSImin大的路徑優，否則執行步驟3;3)如果兩條路徑CDI不等則直接判定CDI大的路徑優否則執行步驟4;4)如果兩條路徑跳數不等則判定跳數小的路徑優，否則判定LRCI大的路徑優。c)目的路由器在所選擇的最優路徑上發起路由回復。路由回復過程在兩種情況下會被發起1)收到目的ID為本路由器ID的rreq包；2)路由器為某到網關的路由請求開啟的路由回復定時器的定時時間到。發起路由回復的步驟為1)選定回復的路徑為路由器記錄的對應該請求的最優路徑；2)構建路由回復(rr印)包並單播發送該rr印包至選定的路徑中的上一跳；3)根據rr印包信息添加路由表項。rr印包的內容包括l)type，其值設為2,代表該包是rr印包；2)length,代表該包長度；3)s_id、d—id、sequence,代表所回復的請求的標識；4)hop,代表路由器在選定的路徑上距源路由器的跳數；5)RSSImin、CDI、LRCI，代表選定的路徑的各項統計信息；6)link—ip[l]~link_ip[k]，代表路徑上各鏈路兩端的IP，k為該路徑跳數，linkjp[i]是選定的路徑上第i跳(從源路由器開始)的鏈路兩端各接口的IP，其中用link—ip[i].forward表示該鏈路上離源路由器遠的那個接口的IP，用link_ip[i].reverse表示該鏈路上離源路由器近的那個接口的IP。根據rrep包的信息添加路由表項的步驟為1)添加正向路徑路由表項，目的地址為240.0.d—id.s—id,下一瑕g為link—ip[m].forward,m為rrep包中hop的值；2)添加反向路徑路由表項，目的地址為240.0.s—id.d_id，下一跳為link—ip[m].reverse。如果路由器是發起回復的路由器，只需要添加反向路徑路由表項，如果路由器是源路由器，只需要添加正向路徑路由表項。目的地址為240.0.ID1.ID2的路由表項代表從ID2路由器發往ID1路由器的數據包査找路由使用的路由表項，每條這樣的路由表項都對應了一條路徑。d)收到路由回復(rr印包)的路由器處理該回復，處理該路由回復的過程中需要添加路由表項。收到路由回復路由器一旦收到rr印包，需要執行以下步驟1)根據s—id判斷本路由器是否是源路由器，如果不是則執行步驟2，否則直接執行步驟4;2)先根據該rr印包的信息添加路由表項，然後根據d—id是否為0判斷該rr印包對應的路由請求是否是到網關的路由請求，如果是則需要記錄路徑信息；3)修改該rr印包內容hop--,然後轉發該包至路徑中該路由器的上一跳，不再執行下面的步驟；4)本路由器為源路由器，根據d—id是否為O判斷該rr印包對應的路由請求是否是到網關的路由請求，如果不是則根據該rr印包的信息添加路由表項即可，不必再執行下面的步驟，否則繼續執行下面的步驟；5)該rr印包對應的請求是本路由器到網關的路由請求，如果該rr印包是路由器收到的第一個相應請求的回覆包，那麼記錄該包的收包時間作為相應請求第一次回復時間、記錄該rr印包的路徑作為本路由器到網關的最優路徑、添加路由表項，如果該rr印包不是路由器收到的相應請求的第一個回復包，則繼續執行步驟6;6)如果該rr印包收包時間距路由器第一次收到對應請求的回覆時間已經超過500ms，則不處理該包，否則使用路徑比較函數判斷該rr印包代表的路徑是否優於當前記錄的本路由器到網關的最優路徑，如果不是則不再進行處理，否則需要更新最優路徑信息與相應路由表項。本發明中，所說的錯誤恢復過程是指當某路徑上一條鏈路發生斷路時，所有使用該鏈路的路徑上的路由器刪除這些失效路徑及它們對應的路由表項，並觸發新的路由發現的過程，步驟為a)—旦路由器R發現到下一跳路由器上某個接口(記該接口IP為X)的鏈路斷路，路由器R需要在其所有記錄的路徑中找到那些下一跳IP是X的路徑，把這些路徑記為失效路徑，然後在各失效路徑上發送路由錯誤(rerr)包至路徑上該路由器的上一跳，rerr包內容是1)type,其值設為3表示該路由包是rerr包；2)length,代表包長；3)s—id、d—id，代表失效路徑的源路由器ID與目的路由器ID;b)路由器R刪除失效路徑的記錄以及這些失效路徑對應的路由表項。c)rerr包將沿失效路徑朝著源路由器轉發，路徑上的路由器一旦收到rerr包，需要在其記錄的路徑中找出源、目的路由器ID分別為s一id、cLid的那條路徑，如果rerr包中s_id的值不是本路由器ID，那麼將該rerr包轉發至該路徑上該路由器的前一跳；d)收到rerr包的路由器還要刪除査找出的路徑以及該路徑對應的路由表項。由於源路由器最終會刪除失效路徑對應的路由表項，所以如果再有數據包需要經該路徑傳輸則會觸發路由守護程序發起一個新的路由請求以建立新的路徑。相對於現有技術，本發明的優點是(1)通過本發明設計的基於源路由器ID和目的路由器ID的路由査找方式和添加路由表項的方式，可以用表驅動來實現源路由，每個mesh網絡內路由器之間的端到端數據流都有各自的傳輸路徑，但不用為每個數據包增加源路由數據頭，這樣就可以不用改變數據包長度。(2)本發明通過綜合使用跳數、RSSI、CDI、LRCI來選擇最優路徑，克服了基於最小跳數路由的不足，可以適合無線網絡環境的動態變化，並進一步有效提高端到端數據流的傳輸速率；(3)本發明還根據寬帶無線mesh接入網內端到端流量大多數是介於網關路由器和帶AP功能路由器之間的特點，每個帶AP功能的路由器都周期性地主動發起到網關的路由發現過程，從而主動及時的更新路徑。(4)本發明的路由方法還可以支持多網關，路由器可以為發往mesh網絡以外的數據包尋找到任一網關的最優路徑。(5)本發明不需要修改當前商用無線網卡的驅動，路由發現過程簡單，快速，開銷小，非常易於實現。圖1是本發明適用的一種寬帶無線mesh接入網的結構示意圖;圖2是本發明的總體結構示意圖；圖3是本發明rr叫、rrep、rerr三種包格式的示意圖；圖4是本發明路由器收到rreq包後的處理流程圖；圖5是本發明路由器收到rrep包後的處理流程圖；圖6是本發明路由器收到rerr包後的處理流程圖；圖7是本發明路徑比較函數的執行流程圖；圖8是本發明路由査找的流程圖中，Rl、R6、R7、R9為帶AP功能的路由器，R2、R3為網關路由器，R4、R5、R8為普通路由器，TlT6代表通過不同路由器接入該mesh網絡的用戶終端，II、12代表有線骨幹網路由器。具體實施例方式下面，結合附圖和具體實施例對本發明作進一步說明。圖2示出了本發明的路由方法的總體結構1)如果路由器收到數據包後基於源路由器ID、目的路由器ID為該數據包查找路由失敗或者帶AP功能的路由器設定的到網關路由請求定時器的定時時間到，那麼路由器將基於源路由器ID、目的路由器ID發起路由發現；2)如果路由器發現鏈路失效，則需要基於源路由器ID、目的路由器ID進行錯誤恢復。其中路由發現過程的步驟是l)源路由器發起路由請求；2)收到路由請求的路由器處理該請求；3)目的路由器發起對該請求的路由回復；4)收到路由回復的路由器處理該回復。圖1示出了本發明適用的其中一種寬帶無線mesh接入網的結構，該mesh網絡由9臺路由器構成，它們的ID為1~9，分別記為Rl、R2……R9。其中Rl、R6、R7、R9為帶AP功能的路由器，R2、R3為網關路由器，R4、R5、R8為普通路由器。該實施例中，每個路由器都配有3個無線接口，分別工作在802.11規定的3個正交信道上，它們的IP配置為1)使用ad-hoc模式且工作在信道i(1=1~3)上的接口配置192.168.25i.ID;2)使用AP模式的接口配置192.168.ID.1。如R4上三個接口IP為192.168.251.4、192.168.252.4、192.168.253.4，Rl上三個接口IP為192.168.251.1、192.168.1.1、192.168.253.1。如果兩個網關路由器R2、R3的WAN口分別配置的IP為100.100.100.1、100.100.100.2，這樣，各路由器上保存的IP與ID對應的列表，即"IP—ID"列表可以表示如下192.168.1.0/24-192.168.252.5-tableseeoriginaldocumentpage13圖8是路由器基於源、目的路由器ID為數據包進行路由査找的流程，其步驟為1)通過査找"IP—ID"表確定數據包源IP、目的IP對應的源路由器IDs—id、目的路由器IDd—id;2)如果d_id為本路由器ID,或者d—id為0且本路由器為網關路由器，那麼直接使用數據包目的IP査找路由表，否則使用240.0.目的路由器ID.源路由器ID，即240.0.d—id.s—id作為目的IP位址查找路由表。舉例說明如果某一時刻路由器R7收到一個用戶數據包，其IP頭中源地址為192.168.7.5，目的地址為192.168.6.8，那麼根據圖8所示流程，R7為該數據包查找路由的步驟為1)査找"IP—ID"表確定192.168.7.5、192.168.6.8對應的ID分別為7、6;2)由於路由器ID為7，而目的ID為6，兩者不等，因此將使用240.0.6.7作為目的地址査找路由表項。如果R7此時沒有目的地址為240.0.6.7的路由表項，那麼R7就馬上發起到R6的路由請求，構建rr叫包並在它的兩個ad-hoc接口向全網廣播。圖3示出了rreq包的格式，一個rreq包包括固定和可變兩個部分。發起請求的路由器發送的rreq包只包括固定部分，它包括1)type,其值設為1，代表該路由包是rreq包；2)length,代筆該包長度，單位是字節；3)sequence,表示該路由請求序列號；4)src—if—ip，代表發起路由請求的路由器發送該rreq包時用的接口的IP;5)src_if_load，代表IP為src—if—ip的接口的數據包流量；6)dst_ip，代表路由請求的目的地址，發起到網關的請求時將該地址設為240.0.0.0;7)hop，代表當前該rreq包被轉發的次數，發起請求的路由器需要將其設為O;8)rssi，代表該rreq包被接收時的RSSI值，發送rreq包的路由器並不為其賦值，其值留給收到該包的路由器在網卡驅動層賦值。可變部分由轉發rreq包的路由器添加，一旦路由器在各接口上轉發rreq包，都需要在包尾添加以下內容l)rssi，填入包固定部分中rssi欄位的值；2)recv—if—ip，代表收到該rreq包的接口的IP;3)recv—if_load，代表IP為recv_if—ip的接口上的數據包流量；4)send_if—ip，代表路由器轉發該rreq包時用的接口的IP;5)send—if—load,代表IP為send—if—ip的接口上的數據包流量。網絡中的路由器最後都可能不止一次的收到此請求的rreq包，只是各包對應的路徑各不相同。以R6為例，如果R6在R7發出請求後的某個時刻第一次收到該請求的rreq包，該rreq包代表的路徑信息有l)路徑上的各鏈路兩端的接□IP:192.168.252.7、192.168.252.4，192.168.253.4、192.168.253.5，192.168.252.5、192.168.252.6;2)該rreq包在各鏈路上被接收時的RSSI:38,62、47;3)各鏈路兩端各接口上的流量(單位為mbps):0.8、1.5，1.6、1.2，2.1、0.9。通過這些信息可以計算出1)路徑跳數為3;2)RSSImin為38;3)各鏈路分別使用信道2、信道3、信道2，所以計算出CDI為0;4)LRCI為0.33。圖4是路由器對rreq包的處理流程，其步驟為1)先通過包中src一ifjp、dst—ip和sequence判斷該請求是否己經過期，如果請求已經過期那麼路由器將不對該包進行處理，否則該請求沒有過期，那麼繼續執行下面的步驟；2)如果d—id不為0，或者d一id為O但本路由器不是網關路由器，那麼執行步驟3)，否則執行步驟5);3)如果該請求是一個新的請求，那麼直接把該rreq包代表的路徑記為該請求對應的最優路徑，並執行步驟4)，否則使用路徑比較函數判斷該rreq包代表的路徑是否優於當前記錄的對應該請求的最優路徑，如果是則更新該最優路徑並執行步驟4)，否則丟棄該包並不再執行下面的步驟；4)如果djd為本路由器ID，那麼路由器需要對該請求進行路由回復，否則在各接口上轉發rreq包。路由器不再執行下面的步驟。5)如果該請求是一個新的請求則記錄該rreq包的路徑信息並為該請求開啟一個時長為500ms的路由回復定時器，否則執行步驟6);6)如果該rreq包的收包時間已經超過了該rreq包對應的請求的定時時間則丟棄該包不進行處理，否則用路徑比較函數判斷該rreq包代表的路徑是否優於當前記錄的最優路徑，如果是則更新當前記錄的最優路徑信息。根據該流程，由於R6第一次收到該請求的rreq包，因此該請求沒有過期而且是一個新的請求，又因為該請求的目的路由器ID不是O，所以R6將記錄該路徑信息作為該請求的最優路徑，由於R6是目的路由器，因此它還將對該請求進行回復。R6對該請求進行回復的步驟為1)根據最優路徑信息構建rrep包；2)添加一條反向路徑路由表項，即目的地址為240.0.7.6，下一跳為192.168.252.5。3)單播發送該rrep包至192.168.252.5，即R5。圖3示出了rrep包的格式，該包包括以下部分1)type，其值設為2，代表該包是rr印包；2)length,代表該包長度；3)s—id、d—id、sequence,代表所回復的請求的標識；4)hop,代表路由器在選定的路徑上距源路由器的跳數；5)RSSImin、CDI、LRCI，代表選定的路徑的各項統計信息；6)link_ip[l]~link—ip[k]，代表路徑上各鏈路兩端的IP，k為該路徑跳數，link—ip[i]是選定的路徑上第i跳(從源路由器開始)的鏈路兩端各接口的IP，其中用linkjp[i].forward表示該鏈路上離源路由器遠的那個接口的IP，用link—ip[i].reverse表示該鏈路上離源路由器近的那個接口的IP。這樣R5將收到該rrep包。圖5是路由器對rrep包的處理流程，步驟為1)根據sjd判斷本路由器是否是源路由器，如果不是則執行步驟2，否則直接執行步驟4;2)先根據該rr印包的信息添加路由表項，然後根據d—id是否為0判斷該rrep包對應的路由請求是否是到網關的路由請求，如果是則需要記錄路徑信息；3)修改該rr印包內容h叩一，然後轉發該包至路徑中該路由器的上一跳，不再執行下面的步驟；4)本路由器為源路由器，根據d—id是否為0判斷該rr印包對應的路由請求是否是到網關的路由請求，如果不是則根據該rr印包的信息添加路由表項即可，不必再執行下面的步驟，否則繼續執行下面的步驟；5)該rr印包對應的請求是本路由器到網關的路由請求，如果該rr印包是路由器收到的第一個相應請求的回覆包，那麼記錄該包的收包時間作為相應請求第一次回復時間、記錄該rrep包的路徑作為本路由器到網關的最優路徑、添加路由表項，如果該rr印包不是路由器收到的相應請求的第一個回復包，則繼續執行步驟6;6)如果該rr印包收包時間距路由器第一次收到對應請求的回覆時間已經超過500ms，則不處理該包，否則使用路徑比較函數判斷該rr印包代表的路徑是否優於當前記錄的本路由器到網關的最優路徑，如果不是則不再進行處理，否則需要更新最優路徑信息與相應路由表項。根據該流程，R5在收到該rrep包後1)添加正向路徑路由表項，即目的地址為240.0.0.6.7，下一跳為192.168.252.6;2)添加反向路徑路由表項，即目的地址為240.0.7.6，下一跳為192.168.253.4;3)將該rrep包中的hop欄位的值減1即賦值為2;4)轉發該rrep包至192.168.253.4即R4。這樣R4也會收到該rrep包並進行類似處理，最後源路由器R7將收到該包，由於R7是目的路由器，所以只需要添加一條正向路由表項，即目的地址為240.0.6.7，下一跳為192.168.252.4。這樣，就建立了一條源路由器R7到目的路由器R6的正向路徑以及一條從R6到R7的反向路徑，之後如果R7收到源、目的IP分別對應源、目的ID為7、6的數據包，就可以査找到目的地址為240.0.6.7的路由表項，其下一跳為192.168.252.4，數據包將被轉發到R4，R4收到該數據包，同樣將查找目的地址為240.0.6.7的路由表項，下一跳為192.168.253.5，最後數據包將轉發到R6的IP為192.168.252.6的接口，根據圖8所示流程，R6路由器對該數據包查找路由的步驟為1)查找"IP—ID"表確定192.168.7.5、192.168.6.8對應的ID分別為7、6;2)由於路由器ID為6，是目的ID，因此直接使用數據包目的IP192.168.6.8查找路由表項。這樣數據包將直接被轉發到IP為192.168.6.8的用戶終端。如果R6在第一次收到該請求的rreq包之後不久又收到了從另一條路徑上發來的該請求的rreq包，假設該rreq包代表的新的路徑的信息是l)路徑上的各鏈路兩端的接口IP:192.168.253.7、192.168.253.8，192.168.252.8、192.168.252.9，192.168.252.9、192.168.252.6;2)該rreq包在各鏈路上被接收時的RSSI:36，55、48;3)各鏈路兩端各接口上的流量(單位為mbps):1.1、1.6，0.6、1.8，1.4、0.9。通過這些信息可以計算出1)路徑跳數為3;2)RSSImin為36;3)各鏈路分別使用信道3、信道2、信道2，所以計算出CDI為O;4)LRCI為0.36。圖7是路徑比較函數的流程，步驟為1)如果兩條路徑的跳數差大於l，那麼直接判定跳數小的路徑優否則執行步驟2;2)如果其中一條路徑的RSSImin或者兩條路徑上的RSSImin均小於一個預先設定的門限Y，而且兩條路徑的RSSImin的差值大於另一個預先設定的門限S，那麼直接判定RSSImin大的路徑優，否則執行步驟3;3)如果兩條路徑CDI不等則直接判定CDI大的路徑優否則執行步驟4;4)如果兩條路徑跳數不等則判定跳數小的路徑優，否則判定LRCI大的路徑優。由於R6不是第一次收到該請求的rreq包，因此R6將使用該路徑比較函數對新的路徑和之前記錄的該請求的最優路徑進行比較，步驟為首先比較跳數，新路徑和當前最優路徑跳數相等都是3跳，因此比較RSSImin，假設預先設定的RSSImin比較門限為30，那麼由於兩條路徑上RSSImin均大於30，因此比較兩路徑的CDI，由於兩條路徑CDI相等，所以再次比較路徑跳數，因為路徑跳數相等，所以比較LRCI，顯然新路徑的LRCI比當前最優路徑的LRCI大，因此判斷新路徑優於當前最優路徑。這樣，R6將更新當前記錄的該請求的最優路徑為新的路徑，然後構建rrep包，添加(更新)目的地址為240.0.7.6的路由表項，其下一跳為192.168.252.9,發送rrep包至192.168.252.9。和第一次的路由回復過程一樣，新路徑上的各路由器R9、R8以及源路由器R7都將收到該rrep包，他們將更新路徑信息以及相應的路由表項，這樣R7和R6之間就建立了新的路徑，之後R7和R6之間的數據包將沿著新路徑傳輸。如果某時刻R9發現其和R6間的兩端接口IP分別為192.168.252.9、192.168.252.6的鏈路發生斷路，那麼R9就會發起錯誤恢復過程，R9首先搜索其本地記錄的各路徑，找到所有使用該鏈路的路徑，如果只有之前記錄的R7到R6的路徑使用該鏈路，那麼R9將構建rerr包，圖3示出了該包格式1)type,其值設為3表示該路由包是rerr包；2)length,代表包長；3)s_id、d—id,代表失效路徑的源路由器ID與目的路由器ID。因此R9發送的rerr包的s一id、d—id分別為7、6，R9將該包發送至該路徑的上一跳即192.168.252.8，然後刪除該路徑及對應的路由表項，即目的地址為240.0.6.7，下一跳為192.168.252.6的路由表項，以及目的地址為240.0.7.6，下一跳為192.168.252.8的路由表項。路由器R8將收到該rerr包。圖6是路由器對rerr包的處理流程，步驟為首先在其記錄的路徑中找出源、目的路由器ID分別為sjd、d—id的那條路徑，如果rerr包中s—id的值不是本路由器ID,那麼將該rerr包轉發至該路徑上該路由器的前一跳，最後路由器需要刪除查找出的路徑的記錄以及該路徑對應的路由表項。根據該流程，R8對收到的該rerr包的處理步驟是l)rerr包指明了失效路徑的源、目的路由器ID分別為7、6，所以R8首先査找出該路徑的記錄信息；2)通過記錄的路徑信息，將該rerr包轉發至路徑中的上一跳即192.168.253.7;3)刪除該失效路徑的記錄信息；4)刪除該失效路徑對應的路由表項。同樣，R7也將收到該rerr包，R7也將刪除該失效路徑的記錄信息以及對應路由表項。這樣，如果R7再收到源、目的IP分別對應源、目的ID為7、6的數據包，將因為無法找到對應路由表項而觸發R7發起一個新的路由請求。權利要求1.一種802.11多接口寬帶無線mesh網絡路由方法，其特徵在於它包括以下部分1)每個路由器預先分配一個固定的ID，並維護一張IP與ID對應的列表；2)路由器基於源路由器ID和目的路由器ID為數據包進行路由查找；3)若路由查找失敗，則基於源路由器ID和目的路由器ID進行路由發現；4)若發現鏈路失效，則基於源路由器ID和目的路由器ID進行錯誤恢復。2.根據權利要求1所述的802.11多接口寬帶無線mesh網絡路由方法，其特徵在於在所述的IP與ID對應的列表中，有一個默認的表項表示不屬於所述mesh網絡的IP位址或IP網段所對應的ID是0，其餘每個表項表示屬於所述mesh網絡的每個IP位址或IP網段由節點號為該表項中的ID的路由器對應管理。3.根據權利要求1所述的802.11多接口寬帶無線mesh網絡路由方法，其特徵在於所述的基於源路由器ID和目的路由器ID的路由査找步驟包括1)通過査找IP與ID對應的列表確定與數據包的源IP和目的IP分別對應的源路由器ID和目的路由器ID;2)如果目的路由器ID為本路由器ID，或者目的路由器ID為O且本路由器為網關路由器，那麼直接使用數據包目的IP查找路由表，否則使用"240.0.目的路由器ID.源路由器ID"作為目的IP査找路由表。4.根據權利要求1所述的802.11多接口寬帶無線mesh網絡路由方法，其特徵在於基於源路由器ID和目的路由器ID進行路由發現的步驟包括1)源路由器發起路由請求；2)收到從不同路徑上轉發過來的路由請求的路由器處理該請求，路由器在處理該請求的過程中使用路徑比較函數來選擇最優路徑；3)目的路由器在所選擇的最優路徑上進行路由回復；4)收到路由回復的路由器處理該回復，處理該路由回復的過程中需要添加路由表項。5.根據權利要求1所述的802.11多接口寬帶無線mesh網絡路由方法，其特徵在於所述的基於源路由器ID和目的路由器ID的錯誤恢復的步驟包括1)發現鏈路失效的路由器在該路由器記錄的所有路徑中查找出使用該失效鏈路的路徑，並在每條失效路徑上發送路由錯誤包，所述路由錯誤包包含了失效路徑的源路由器ID和目的路由器ID;2)發現鏈路失效的路由器刪除各失效路徑的記錄以及這些失效路徑對應的路由表項；3)收到路由錯誤包的路由器根據該路由錯誤包中的源路由器ID和目的路由器ID在路由器記錄的路徑中查找出對應路徑，如果路由器ID不是源路由器ID，那麼根據査找出的對應路徑轉發該路由錯誤包；4)收到路由錯誤包的路由器刪除査找出的對應路徑的記錄以及對應的路由表項。6.根據權利要求4所述的802.11多接口寬帶無線mesh網絡路由方法，其特徵在於所述的路徑比較函數採用跳數、接收信號強度指示、路徑信道差異指數、路徑剩餘容量指數來比較兩條路徑的優劣，所述路徑比較的步驟包括1)判斷兩條路徑的跳數差是否大於1，如果是，則直接判定跳數小的路徑優於跳數大的路徑並不再執行後面的步驟；如果不是，則執行後一步驟；2)計算兩條路徑各自的接收信號強度指示的最小值RSSImin，如果兩條路徑的RSSImin均大於一個預先設定的門限值Y，或者兩條路徑的RSSImin的差值不大於另一個預先設定的門限值S，則執行後一步驟；否則直接判定RSSImin的值大的那條路徑優於另一條路徑並不再執行後面的步驟；3)計算兩條路徑各自的路徑的信道差異指數，如果兩條路徑的路徑的信道差異指數相等則進入後一步驟；否則直接判定路徑的信道差異指數值大的路徑優於另一條路徑並不再執行後面的步驟；其中，所述路徑的信道差異指數的計暫/入二麼、式為formulaseeoriginaldocumentpage3路徑信道差異指數formulaseeoriginaldocumentpage3式中，N為路徑跳數，Nl，N2，N3分別為使用802.11中3個正交信道的鏈路數目；4)如果兩條路徑跳數不等，那麼直接判定跳數小的路徑優於跳數大的路徑;否則計算兩條路徑各自的路徑剩餘容量指示並判定路徑剩餘容量指數值大的路徑優於路徑剩餘容量指數值小的路徑，所述路徑剩餘容量指數值的計算公式為路徑剩餘容量指數formulaseeoriginaldocumentpage3式中，N為路徑跳數，4'，V為路徑上第k條鏈路的兩個接口上的流量。7.根據權利要求4所述的802.11多接口寬帶無線mesh網絡路由方法，其特徵在於所述的在處理路由回復過程中添加的路由表項使用的目的地址為"240.0.目的路由器ID.源路由器ID"，該地址是路由器為從源路由器發往目的路由器的數據包在査找路由時使用的目的地址。全文摘要本發明公開了一種802.11多接口寬帶無線mesh網絡路由方法，屬於寬帶無線mesh接入網
技術領域：
。本發明的路由方法包括以下部分每個路由器預先分配一個固定的ID，並維護一張IP與ID對應的列表；路由器基於源路由器ID和目的路由器ID為數據包進行路由查找；若路由查找失敗，則基於源路由器ID和目的路由器ID進行路由發現；若發現鏈路失效，則基於源路由器ID和目的路由器ID進行錯誤恢復。本發明的路由方法簡單方便、快速，開銷小，非常易於實現，且能夠有效提高端到端速率。文檔編號H04W40/02GK101594658SQ200910100390公開日2009年12月2日申請日期2009年7月10日優先權日2009年7月10日發明者雲催,呂思達,斌周,峰王,曉王,趙志峰,陳琴琴申請人:浙江大學