[發明專利]無線Mesh網絡多播部分重疊信道分配與調度方法

有效

• 申請號: 201410072216.9
• 申請日: 2014-03-02
• 公開（公告）號: CN103796325B
• 公開（公告）日: 2017-03-01
• 發明（設計）人: 石文孝;金鳳;鄭宇;王繼紅;崔克強;許銀龍
• 申請（專利權）人: 吉林大學
• 主分類號: H04W72/06
• 分類號: H04W72/06;H04W72/12
• 代理公司: 長春吉大專利代理有限責任公司22201
• 代理人: 王淑秋

1.一種無線Mesh網絡多播部分重疊信道分配與調度方法，其特征在于包括以下步驟：

步驟1）構建多播樹；在多播樹中將節點按照到多播源節點的跳數分成不同等級，其中多播源節點為網關節點，在第0級；對于在第i級的任意一個節點，定義與其相連的在第i+1級的所有節點為該節點的子節點，該節點為這些子節點唯一的父節點；

步驟2）根據構建好的多播樹，利用無線廣播優勢對多播樹中的父節點和其子節點進行鄰居-接口綁定，父節點與其所有子節點之間的鏈路構成了需要分配相同信道的鏈路集；然后根據各鏈路集距離多播源節點的跳數，對多播樹中各鏈路集進行升序排列確定信道分配的次序；所述鏈路集距離多播源節點的跳數定義為鏈路集的各個端點距離多播源節點跳數的最小值；

步驟3）按照步驟2）中鏈路集的順序，為各未分配信道的鏈路集分配滿足無干擾約束條件的部分重疊信道，若某鏈路集不存在符合無干擾約束條件信道，則本輪信道分配中不為該鏈路集分配信道；按照上述方式遍歷多播樹中所有未分配信道的鏈路集后，本輪無干擾信道分配結束；將多播樹中本輪已經分配信道的鏈路集看成一個無干擾鏈路集LS₁，從未分配信道的鏈路集中劃去此無干擾鏈路集；

定義需要分配相同信道的鏈路集為L，則L的滿足無干擾約束條件的無干擾信道集C_L獲得方法如下：

a、對于L中任意一條鏈路l_i=(a,b)，i=1,2，......，m，節點a表示鏈路l_i的發送節點，節點b表示鏈路l_i的接收節點，定義鏈路l_i的潛在干擾范圍為，則表示為：

IRli=D(a,I0)∪D(b,I0)]]>

其中I₀表示信道間隔τ=0時的干擾范圍，D(a,I₀)表示以節點a為圓心以I₀為半徑的圓形區域，D(b,I₀)表示以節點b為圓心以I₀為半徑的圓形區域；

b、定義鏈路l_i的潛在干擾鏈路集為：

N(l_i)＝N(a)∪N(b)

其中N(a)是由滿足如下條件的鏈路組成的鏈路集：1）鏈路的接收節點在D(a,I₀)內；2）該鏈路已經被分配信道；N(b)是由滿足如下條件的鏈路組成的鏈路集：1）鏈路的發送節點在D(b,I₀)內；2）該鏈路已經被分配信道；

c、設n_j=(c,d)為N(l_i)內任意一條鏈路，節點c表示鏈路n_j的發送節點，節點d表示鏈路n_j的接收節點；網絡中有11條可用信道；對于鏈路l_i，定義一個11×11的鏈路互干擾矩陣，表示鏈路l_i與鏈路n_j之間的互干擾情況；鏈路l_i使用信道x，鏈路n_j使用信道y，R(l_i,n_j)表示鏈路l_i和n_j之間的歐式距離，若R(l_i,n_j)小于等于信道間隔τ為x-y的干擾范圍I_τ＝I_|x-y|，表示鏈路l_i和n_j在彼此的干擾范圍內，兩條鏈路之間存在干擾，否則認為兩條鏈路互不干擾，用1表示存在干擾，0表示不存在干擾，則矩陣的第x行第y列元素m_xy表示如下：

mxy={1R(li,nj)≤I|x-y|0R(li,nj)>I|x-y|1≤x,y≤11]]>

R(l_i,n_j)＝min(R(a,d),R(b,c))

其中R(a,d)表示節點a和節點d的歐式距離，R(b,c)表示節點b和節點c的歐式距離；

d、根據鏈路l_i和鏈路n_j的互干擾矩陣和鏈路n_j的信道分配向量得到鏈路l_i相對于鏈路n_j的無干擾信道集

其中是一個11×1的信道分配向量；若n_j使用第k條信道傳輸數據，則中第k個向量等于1，否則等于0；

e、按照上述方法遍歷鏈路l_i的潛在干擾鏈路集N(l_i)內所有鏈路，取鏈路l_i相對于潛在干擾鏈路集N(l_i)內所有鏈路的無干擾信道集的交集為鏈路l_i的無干擾信道集。同理求得需要分配相同信道的鏈路集L內其他鏈路的無干擾信道集，取鏈路集L內所有鏈路的無干擾信道集交集作為L的無干擾信道集，則L的無干擾信道集C_L為：

CL=Cl1∩Cl2∩···Cli∩...∩Clml1,l2,...li..,lm∈L]]>

4）重復步驟3），為各未分配信道的鏈路集進行第二輪分配滿足無干擾約束條件的部分重疊信道；第二輪分配結束后將多播樹中本輪已經分配信道的鏈路集看成一個無干擾鏈路集LS₂，從未分配信道的鏈路集中劃去此無干擾鏈路集；以此類推，對各未分配信道的鏈路集進行第三、四、……N輪滿足無干擾約束條件的部分重疊信道分配，直至多播樹中未分配信道的鏈路集為空集，形成N個無干擾鏈路集LS₁，LS₂，LS₃，…，LS_N；多播樹中所有鏈路都被分配信道時，多播部分重疊信道分配結束；

5）采用靜態分時調度的方法調度各無干擾鏈路集LS₁，LS₂，LS₃，…，LS_N，實現多播樹中所有鏈路的無干擾數據傳輸。