[發(fā)明專利]基于構(gòu)建二信道連通下k點連通的拓撲控制方法

有效

• 申請?zhí)枺?/td>: 201611093640.7
• 申請日: 2016-12-02
• 公開（公告）號: CN106792744B
• 公開（公告）日: 2019-10-11
• 發(fā)明（設(shè)計）人: 盛敏;陳雯;李建東;王璽鈞;李軒;劉豹
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W84/18;H04L12/24
• 代理公司: 陜西電子工業(yè)專利中心 61205
• 代理人: 王品華;朱紅星

1.基于構(gòu)建二信道連通下k點連通的拓撲控制方法，包括如下步驟：

(1)初始化網(wǎng)絡(luò)為k點連通，網(wǎng)絡(luò)中每個節(jié)點u分別獲得一跳和兩跳節(jié)點的序列號和位置信息，k≥2；

(2)根據(jù)序列號和位置信息建立局部兩跳拓撲子圖其中，為的節(jié)點集合，為的邊集合；

(3)基于局部兩跳拓撲子圖每個節(jié)點u建立局部k-1點連通拓撲子圖G_u；

(3a)初始化局部k-1點連通拓撲子圖節(jié)點u根據(jù)G_u找到其鄰節(jié)點集合PN_u，并構(gòu)建k-1點連通拓撲子圖SN_u；

(3a1)初始化第一k-1點連通拓撲子圖的節(jié)點集合為將節(jié)點集合中任意兩點在G_u中對應(yīng)的邊賦予的邊集合即其中，E(x,y)∈E(G_u)，{u}表示節(jié)點u組成的集合，PN_u為節(jié)點u在中的一跳鄰節(jié)點集合；

(3a2)運用最大流算法判斷是否為k-1點連通：若是，則跳到步驟(4)，否則，執(zhí)行步驟(3b)；

(3b)初始化第二k-1點連通拓撲子圖

(3b1)判斷是否為空集：若是，則跳到步驟(3c)，否則，執(zhí)行步驟(3b2)；

(3b2)運用最大流算法判斷是否為k-1點連通：若是，則跳到步驟(4)；否則，按照節(jié)點序列號將中的節(jié)點m加入頂點集合即同時將節(jié)點集合中任意兩節(jié)點在中對應(yīng)的邊賦予即返回步驟(3b1)，其中，

(3c)初始化第三k-1點連通拓撲子圖

(3c1)運用最大流算法判斷是否為k-1點連通：若是，則跳到步驟(4)，否則，執(zhí)行步驟(3c2)；

(3c2)節(jié)點u根據(jù)步驟(1)和步驟(2)獲知其h跳鄰節(jié)點的信息，得到V(G_u)的所有鄰節(jié)點按照節(jié)點序列號將中的節(jié)點w依次加入的節(jié)點集合和G_u的節(jié)點集合V(G_u)，即同時將節(jié)點w與V(G_u)中節(jié)點的關(guān)聯(lián)邊加入的邊集合和G_u的邊集合，即返回步驟(3c1)，其中，c∈V(G_u)，且E(c,w)為節(jié)點w與V(G_u)中任意節(jié)點c的關(guān)聯(lián)邊；

(4)根據(jù)局部k-1點連通拓撲子圖G_u，每個節(jié)點u計算任意兩個有連接關(guān)系的節(jié)點x,y之間的鏈路能耗權(quán)重w_p(x,y)＝P_x,y和鏈路距離權(quán)重w_d(x,y)＝d_x,y,其中，x,y∈V(G_u)，P_x,y為任意兩個有連接關(guān)系的節(jié)點x,y之間直接傳輸所需要的最小發(fā)送功率，d_x,y是任意兩個有連接關(guān)系的節(jié)點x,y之間的歐氏距離；

(5)網(wǎng)絡(luò)中每個節(jié)點u構(gòu)建局部生成子圖S＝(V(S),E(S))，并根據(jù)局部生成子圖S得到每個節(jié)點u的邏輯沖突節(jié)點集合LCN_u，其中V(S)表示S的節(jié)點集合，E(S)表示S的邊集合；

(6)每個節(jié)點u根據(jù)其他節(jié)點v發(fā)來的拓撲信息更新自己的局部生成子圖S和邏輯沖突鄰節(jié)點集合LCN_u，將局部生成子圖S上的一跳鄰節(jié)點作為邏輯鄰節(jié)點，構(gòu)成邏輯鄰節(jié)點集合：其中，v∈V(S)且E(u,v)∈E(S)，即節(jié)點v屬于局部生成子圖S的節(jié)點集合V(S)且節(jié)點u和v對應(yīng)的邊E(u,v)屬于局部生成子圖S的邊集合E(S)；

(7)網(wǎng)絡(luò)中每個節(jié)點u確定自己的發(fā)射功率，即將發(fā)射功率調(diào)整為能夠覆蓋到所有邏輯鄰節(jié)點所需要的最小功率：其中，P_u,v表示節(jié)點u到節(jié)點v所需的最小發(fā)射功率；

(8)將網(wǎng)絡(luò)中的所有節(jié)點以及每個節(jié)點與自己的邏輯鄰節(jié)點間的鏈路組合起來，構(gòu)成最終的全網(wǎng)拓撲，即G＝(V(G),E(G))，其中，V(G)為網(wǎng)絡(luò)中所有節(jié)點，E(G)為網(wǎng)絡(luò)中所有邊；

(9)使用貪婪染色算法對已構(gòu)建的最終全網(wǎng)拓撲G中的每個節(jié)點u進行信道分配。