[發明專利]一種工業無線網絡中基于最大匹配的時隙信道分配方法

有效

• 申請號: 201410286957.7
• 申請日: 2014-06-24
• 公開（公告）號: CN104093208B
• 公開（公告）日: 2017-11-17
• 發明（設計）人: 王恒;王平;夏樞洋;劉鋒
• 申請（專利權）人: 重慶郵電大學
• 主分類號: H04W72/04
• 分類號: H04W72/04
• 代理公司: 重慶市恒信知識產權代理有限公司50102
• 代理人: 劉小紅

1.一種工業無線網絡中基于最大匹配的時隙信道分配方法，其特征在于包括以下步驟：

101、工業無線網絡進行初始化，設定初始時隙k_初始＝0，將此時初始時隙k＝0對應的調度表part進行初始化，即part＝0；

102、統計工業無線網絡時隙幀slotframe中初始時隙k_初始＝0到k時隙為止從葉子節點匯聚到主節點PAN協調器總的流量數q₀(k)及工業無線網絡中總的流量數Q，當q₀(k)＝Q時，則表明調度表part已經生成，根據調度表進行時隙信道分配，結束；當q₀(k)≠Q時，則表明調度表還沒有完全生成，跳轉至步驟103；

103、獲取k時隙時的網絡拓撲圖及k時隙時的物理連通圖，并采用最大匹配算法匈牙利算法求得k時隙時的網絡拓撲圖的免多沖突鏈路集合VMCL(k)；

104、將步驟103求得的免多沖突鏈路集合VMCL(k)與k時隙時的物理連通圖進行對比，以k時隙物理連通圖作為參考，對VMCL(k)鏈路集合進行修正，剔除VMCL(k)鏈路集合中存在而k時隙物理連通圖中不存在的鏈路，將k時隙物理連通圖中存在而VMCL(k)鏈路集合中不存在且與現有VMCL(k)鏈路集合不產生沖突的鏈路填補進VMCL(k)鏈路集合中，由此形成沖突干擾圖IC(k)＝{V_I(k),E_I(k)}，其中V_I(k)表示沖突干擾圖IC(k)中節點的集合，E_I(k)表示沖突干擾圖IC(k)中鏈路的集合；

105、將步驟104中得到的沖突干擾圖IC(k)＝{V_I(k),E_I(k)}采用順序點著色算法著色，選取質量較好的信道制作成抗干擾信道序列對著色的點進行信道的分配，將上述過程中分配得到的時隙和信道信息的填入調度表part，將所述調度表part進行升級更新，網絡根據調度表中的時隙信道分配信息進行調度運行。

2.根據權利要求1所述的工業無線網絡中基于最大匹配的時隙信道分配方法，其特征在于：步驟103中的最大匹配算法匈牙利算法步驟如下：

201、將k時隙時的網絡拓撲圖頂點劃分為兩個互不相交子集X,Y,且拓撲圖中的每條邊的所關聯的兩個頂點分別屬于這兩個不同的頂點集，由此形成該網絡拓撲具有二部劃分(X,Y)的二分圖,在二分圖中任意選定一初始匹配集合M；

202、若頂點集X或Y中每一個頂點都在匹配集合M中，則稱匹配集合M飽和，若匹配集合M飽和，則跳至步驟207，若匹配集合M不飽和，則跳至步驟203；

203、若圖中一頂點不在匹配集合M中,則稱該頂點為非M飽和點,在集合X中任意選定初始匹配集合M的一個非M飽和點x，將x存入集合X對應的非飽和點集合S中，即S＝{x}，集合Y對應的非飽和點集合T為空集，即T＝φ；

204、獲取非飽和點集合S中所有與x相鄰的點的集合N(S)，若N(S)＝T，則跳轉至步驟207；否則任選一點y∈N(S)-T；

205、若y為匹配集合M的一個頂點，即y為M飽和點，則轉到步驟206，否則選取一條從x到y的M可增廣路P，將集合M與集合P的并集去除集合M與集合P的交集后的集合作為新的匹配集合M，即M＝M⊕P，轉到步驟202；

206、由于y是匹配集合M中的M飽和點，則匹配集合M中必然存在一條邊{y,u}，將這條邊的另一個頂點u加入到X對應的非飽和點集合S中，即S＝S∪{u}，將y加入到Y對應的非飽和點集合T中，即T＝T∪{y}，最后從頂點u的相鄰的點的集合中選出非M飽和點加入到N(S)中，轉到步驟/204；

207、結束尋找，得到最大匹配集合M'。

3.根據權利要求1所述的工業無線網絡中基于最大匹配的時隙信道分配方法，其特征在于：所述步驟105中的順序點著色算法步驟中，還包括采用選擇函數Q_i(k)＝max{Q_j(k)|n_j∈ch(p_i)∧q_j(k)≠0}，對節點i的流量Q_i(k)進行逆序排列的步驟，其中ch(p_i)表示節點p_i的所有子節點。