[發明專利]認知AdHoc網絡中構建K信道連通的分布式拓撲方法

有效

• 申請號: 201610369203.7
• 申請日: 2016-05-30
• 公開（公告）號: CN106658523B
• 公開（公告）日: 2019-10-11
• 發明（設計）人: 盛敏;李軒;劉豹;孫紅光;王璽鈞;李建東;陳雯
• 申請（專利權）人: 西安電子科技大學;中國電子科技集團公司第五十四研究所
• 主分類號: H04W16/14
• 分類號: H04W16/14;H04W72/08;H04W84/18
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華

1.認知Ad Hoc網絡中構建K信道連通的分布式拓撲方法，包括如下步驟：

(1)初始化網絡為k點連通，k≥2，網絡中每個節點u分別獲得一跳和兩跳鄰接點的序列號和位置信息，即網絡中每個節點u以最大發射功率P_max向位于距離自己傳輸半徑范圍內的所有節點分別廣播一次第一節點信息HELLO-1包和第二節點信息HELLO-2包，并接收一跳鄰節點發送的HELLO-1包和HELLO-2包，該HELLO-1包中包括u節點的序列號和位置信息，HELLO-2包中含有u的所有一跳鄰節點的序列號和位置信息；

(2)根據步驟(1)中的序列號和位置信息建立局部兩跳拓撲子圖并計算中任意兩個有連接關系的節點x,y之間的鏈路能耗權重w_p(x,y)和鏈路距離權重w_d(x,y)：

(2a)每個節點u根據接收的一跳鄰節點的第一節點信息HELLO-1包和第二節點信息HELLO-2包，獲取并記錄該HELLO-1包和HELLO-2包中節點的序列號和位置信息，這些鄰節點構成兩跳鄰節點集其中所述HELLO-1包中包括u節點的序列號和位置信息，所述HELLO-2包中含有u的所有一跳鄰節點的序列號和位置信息；

(2b)每個節點u根據自己的位置信息以及兩跳鄰節點的位置信息，計算任意兩個節點x,y之間直接傳輸所需要的最小發射功率其中，β為接收信噪比門限值，根據接收機的靈敏度和誤碼率要求確定，α為路徑損耗因子，d_x,y是節點x,y之間的歐式距離，若P_x,y小于節點的最大發射功率P_max，則確定節點x,y之間存在連接關系；否則，節點x,y之間不存在連接關系；

(2c)每個節點u根據兩跳鄰節點之間的連接關系，建立局部兩跳拓撲子圖其中局部拓撲子圖的節點集合為局部拓撲子圖的邊集合為:即對于中的任意兩個節點當時，邊

(2d)根據局部兩跳拓撲子圖，計算每個節點u中任意兩個有連接關系的節點x,y之間的鏈路能耗權重：w_p(x,y)＝P_x,y，其中，P_x,y為任意兩個有連接關系的節點x,y之間直接傳輸所需要的最小發送功率；

(2e)根據歐式距離，計算節點u中任意兩個有連接關系的節點x,y之間的距離權重：w_d(x,y)＝d_x,y，其中，d_x,y是任意兩個有連接關系的節點x,y之間的歐氏距離；

(3)網絡中每個節點u構建局部生成子圖S_u：

(3a)初始化每個節點局部生成子圖S_u的節點集合V(S_u)為局部兩跳拓撲子圖中的所有節點，初始化每個節點局部生成子圖S_u的邊集合E(S_u)為空集；

(3b)基于局部兩跳拓撲子圖每個節點u根據鏈路能耗權重w_p(x,y)，構建以u為根，遍及局部兩跳拓撲子圖中所有節點的最短路徑樹T_u＝(V(T_u),E(T_u))，其中為局部兩跳拓撲子圖中的所有節點，E(T_u)為構成最短路徑樹的所有邊，并將這些邊記錄到局部生成子圖的邊集合E(S_u)中，即E(S_u)＜＝E(T_u)∪E(S_u)；

(3c)網絡中的每個節點u根據最短路徑樹T_u找到與自己沖突的節點，構成沖突節點集合CN_u，并根據CN_u和構建沖突子圖CS_u＝(V(CS_u),E(CS_u))，其中V(CS_u)＝CN_u，

(3d)判斷沖突子圖CS_u是否為k-1點連通：若是，則將CS_u放入到沖突子圖集合{CS_u}中；否則，在局部兩跳拓撲子圖中構建k-1點連通沖突子圖令即將放入到沖突子圖集合{CS_u}中；所述構建k-1點連通沖突子圖的步驟如下：

(3d1)根據的沖突節點集合CN_u，添加沖突節點v的鄰節點x和節點對(v,x)所連接的邊E(v,x)到中，形成其中v∈CN_u；

(3d2)判斷是否與k-1點連通：若成立，令否則，返回到步驟(3d1)；

(3e)判斷k-1≥2是否成立：若成立，則執行步驟(3f)，否則，跳到步驟(3m)；

(3f)初始化i＝2，其中i表示沖突子圖處于第i層；

(3g)初始化j＝1，其中j表示沖突子圖CS_u中第j個沖突節點；

(3h)令其中{CS_u}_j表示在沖突子圖CS_u的第j個節點的沖突子圖，表示第i-1層沖突子圖；

(3i)對于所有的節點在中找到相應的沖突節點集合CN_uv，根據CN_uv和構建第i層沖突子圖其中的節點集邊集

(3j)判斷是否為k-i點連通沖突子圖：若成立，則將并入到沖突子圖集合{CS_u}中，否則，構建k-i點連通沖突子圖令并將并入到集合{CS_u}中；所述構建k-i點連通沖突子圖的步驟如下：

(3j1)根據的沖突節點集合CN_uv，添加沖突節點w的鄰節點x和節點對(w,x)所連接的邊E(w,x)到中，形成其中w∈CN_uv；

(3j2)判斷是否k-i點連通：若成立，則令否則返回到步驟(3j1)；

(3k)判斷j是否滿足j＝|{CS_u}|：若成立，執行步驟(3l)，否則，j＝j+1，跳到步驟(3h)；

(3l)判斷i是否滿足i＝k-1：若成立，執行步驟(3m)，否則，i＝i+1，跳到步驟(3g)；

(3m)對集合{CS_u}中的所有沖突子圖利用分布式二信道連通算法DBCC構建生成子樹S_u＝(V(S_u),E(S_u))，其中V(S_u)表示S_u的節點集，E(S_u)表示S_u的邊集，按如下步驟進行：

(3m1)對于集合{CS_u}中的每個沖突子圖構造相應的局部生成子圖T_u'＝(V(T_u'),E(T_u'))；

(3m2)更新局部生成子圖S_u的邊集E(S_u)，即E(S_u)＜＝E(T_u')∪E(S_u)，更新局部生成子圖S_u的邊集V(S_u)，即V(S_u)＜＝V(T_u')∪V(S_u)，并將節點V(T_u')記錄到邏輯沖突鄰居集LCN_uv中，即LCN_uv＝V(T_u')，然后節點u通過洪泛的方式把LCN_uv和E(S_u)的拓撲信息發送給S_u中的所有節點；

(3n)每個節點u根據其他節點發來的拓撲信息更新自己的局部生成子圖S_u和邏輯沖突鄰居集LCN_uv，將局部生成子圖S_u上的一跳鄰節點v作為邏輯鄰節點，并構成邏輯鄰節點集：LCN_u＝{v∈V(S_u)|(u,v)∈E(S_u)}；

(3p)更新邊集信息E(S)＝E(S)∪E(S_u)，更新邏輯鄰節點信息LCN_u＝V(S_u)，其中E(S)表示網絡中所有節點生成總的生成圖的邊集，LCN_u表示節點u的邏輯鄰節點集合；

(4)網絡中每個節點u確定自己的發射功率，即將發射功率調整為能夠覆蓋到所有邏輯鄰節點所需要的最小功率：

(5)將網絡中的所有節點以及每個節點與自己的邏輯鄰節點間的鏈路組合起來，構成最終的全網拓撲，即G＝(V(G),E(G))，其中V(G)為網絡中所有節點，E(G)＝{(u,v)|u∈V(G),v∈LCN_u}，其中E(G)表示網絡G中的邊集；

(6)使用貪婪染色算法對已構建的最終全網拓撲中的每個節點u進行信道分配，按如下步驟進行：

(6a)節點u向邏輯沖突鄰居集LCN_u中的所有節點用最大發送功率通過洪泛的方式在公共控制信道上發送請求分配信道包RAC；

(6b)邏輯沖突鄰居集LCN_u中的節點在收到RAC包后，用最大發送功率通過單播的方式把回饋信道分配包AC發給節點u，告知已經選擇的信道；

(6c)節點u收集所有LCN_u中的節點回饋的AC包，并從還未被占用的信道中選擇主用戶占用概率最小的信道，作為自己的可用信道。

2.根據權利要求1所述的認知Ad Hoc網絡中構建K信道連通的分布式拓撲方法，其中步驟(3b)中的最短路徑樹T_u使用Dijkstra算法或Bellman-Ford算法構建。