[發明專利]一種基于跨層設計的分布式認知無線電網絡路由方法

無效

• 申請號: 200810241018.5
• 申請日: 2008-12-24
• 公開（公告）號: CN101437273A
• 公開（公告）日: 2009-05-20
• 發明（設計）人: 周賢偉;王建萍;劉濤;林琳;王超;楊裕亮
• 申請（專利權）人: 北京科技大學
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04W40/16;H04B17/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于跨層設計的分布式認知無線電網絡路由方法，其特征在于：方法分為著色多重圖模型的建立、路由的跨層設計、著色多重圖和節點接口數的更新三個步驟；

(a)著色多重圖模型的建立：給每個信道一個唯一的顏色標識，當兩個節點彼此在對方的發射范圍之內，當前又有公共的可用信道，則它們互為潛在的鄰居節點，構造著色多重圖是在每對潛在的鄰居節點之間連邊，并用它們的公共信道對應的顏色來對邊著色，得到了反映網絡拓撲和當前可用信道的著色多重圖G＝(V，E)，其中V表示頂點集，對應于網絡中的節點集，E表示邊集，對應于網絡中的鏈路集；定義權函數μ：E(G)→R⁺以及顏色標號函數k：E(G)→{Ch1，Ch2，…，ChN}，其中權函數是定義在圖G的邊集上的函數，值域為正實數集，權函數將圖G上的每一條邊對應于一個正實數，顏色標號函數也是定義在邊集上的函數，值域為信道集，顏色標號函數將圖G上的每一條邊與一種顏色對應；

(b)路由的跨層設計：在認知無線電網絡中，用頻譜的不確定性要將網絡層和MAC層進行跨層設計，充分利用網絡節點的無線電接口，在選擇路由的同時，選擇鄰居節點間的通信信道；跨層設計路由要滿足可行性和保證路徑最短；另外還要局部優化路徑上相鄰鏈路之間的干擾，路徑上相鄰鏈路之間的干擾稱為鄰跳干擾，采用路徑上最大連續同色邊數對鄰跳干擾進行量化；對鄰跳干擾的局部優化，是指在選擇下一跳節點時，在優化跳數的前提下，選擇當前的最大連續同色邊數最小的路徑；

通過算法可以得到源節點s和目的節點t之間最短的可行路徑p，同時局部優化p上的鄰跳干擾，算法的具體步驟如下：

Step1：對算法的參數進行初始化，用l(x)表示算法選擇的從s到x的最短路徑的跳數，則l(s)＝0，對G中除s之外的其它節點y，令l(y)＝∞，用E(x)和c(x)分別表示算法選擇的從s到x的最短路徑上的最后一條邊和從s到x的最短路徑上的連續同色邊數，則對G中的任意節點x，在初始化階段有c(x)＝0，對G中的任意一條邊e，將其權值賦為1，得到μ(e)＝1，初始化階段其中R是一個動態變化的節點集合，當確定了源節點s到某節點的最優路徑，把該點加入到R中；

Step2：對于所有在V(G)但不在R中的節點，選擇一個節點v，使得該節點v對應的l(v)值最小，當有多于一個節點，根據下標的降序選擇具有最小c(v)的第一個節點；

Step3：令R＝R∪{v}，當節點v只有一個接口，則對于關聯于v的但顏色標號不等于k(E(v))的邊，將其權重變為∞；

Step4：當t∈R，則算法結束，輸出從s到t的反向最優路徑：t→p(t)→p(p(t))→…→s，其中p(v)表示算法選擇的從s到v的最短路徑上節點v前面的鄰居節點；否則，對任意在V(G)但不在R中的節點w，檢查是否要將節點w前面的鄰節點p(w)更新為v，記v與w之間權重為1的邊分別為e₁，e₂，…，e_m；

當l(w)＜l(v)+1，

或者l(w)＝l(v)+1且k(E(p(w)))≠k(E(w))，

或者l(w)＝l(v)+1且k(E(p(w)))＝k(E(w))且c(p(w))＜c(v)，

則說明將p(w)更新為v既不能減小源節點s到節點w的跳數，也不能在跳數相同的情況下減小節點w前的連續同色邊數，直接轉Step2；

否則，當以上條件均不成立，則說明將p(w)更新為v或者能減小源節點s到節點w的跳數，或者是在跳數相同的情況下減小了節點w前的連續同色邊數，則將w之前的節點更新為v，得到p(w)＝v，同時更新l(w)＝l(v)+1，對于e₁，e₂，…，e_m，按照下標的降序檢查這m條邊，選擇滿足k(e_i)≠k(E(v))的具有最小下標的e_i，并將e_i作為v與w之間的連邊，得到E(w)＝e_i，當m＝1且k(e_i)＝k(E(v))，選擇e₁作為v與w之間的連邊，得到E(w)＝e₁，同時更新c(w)＝c(v)+1，轉Step2；

(c)著色多重圖和節點接口數的更新：由于節點接口數的限制以及可用頻譜的動態性，在可用頻譜發生變化以及每個節點對的傳輸任務開始和結束時，著色多重圖的拓撲以及節點接口數都要進行更新，具體的更新規則如下：

(c1)節點接口數的更新規則：

對于所選的從s到t的最短的可行路徑p，p上每個節點v的接口數減去v所關聯的邊的顏色數，對于v＝s和v＝t，v所關聯的邊的顏色數為1，則IN(v)＝IN(v)-1，其中IN(v)表示節點v的接口數；對于p上任意一個中間節點v，當v前后的邊是同色邊時，v所關聯的邊的顏色數為1，當v前后的邊顏色不相同時，v所關聯的邊的顏色數為2，因此有

IN(v)=IN(v)-2c(v1)=0IN(v)-1c(v1)>0,]]>

其中v₁是p上v之后的鄰居節點；

當s到t的路徑p上的傳輸結束時，p上每個節點v的接口數要加上v所關聯的邊的顏色數，對于v＝s和v＝t，IN(v)＝IN(v)+1，對于p上任意一個中間節點v，

IN(v)=IN(v)+2c(v1)=0IN(v)+1c(v1)>0]]>

其中v₁是p上v之后的鄰居節點；

(c2)著色多重圖的更新規則：

用G₁和G₂表示當前圖和更新后的圖，p是算法選擇的最短的可行路徑，E_p表示p的邊集，令E₊和E_-分別表示那些最新可用和最新不可用的邊的集合；注意到E₊和E_-中的邊被它的端點以及顏色所唯一確定，選定路徑p后，G₁應當按照下面的公式被更新為G₂：

G₂＝G₁+E₊-E_--E_p。