无线Mesh网络多播部分重叠信道分配与调度方法

摘要

本发明涉及一种无线Mesh网络多播部分重叠信道分配与调度方法，该方法主要包括以下步骤：构建多播树；根据构建好的多播树，利用无线广播优势对多播树中的父节点和其子节点进行邻居‑接口绑定，使用相同接口的链路构成了需要分配相同信道的链路集；根据各链路集距离多播源节点的跳数，对多播树中各链路集进行升序排列确定信道分配的次序；按照链路集的顺序为各未分配信道的链路集进行多轮满足无干扰约束的部分重叠信道分配，形成多个无干扰链路集；采用静态分时调度的方法调度各无干扰链路集，实现多播树中所有链路的无干扰数据传输。本发明可以避免隐藏信道问题，增加同时传输链路数，实现所有链路无干扰传输，提高网络吞吐量及频谱利用率。

主权项

一种无线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的潜在干扰范围为则表示为：${\mathrm{IR}}_{l_i}=D(a,I_0)\cup D(b,I_0)$其中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表示如下：$m_{xy}=\left\{\begin{array}{cc}1& R(l_i,n_j)\le I_{\left|x-y\right|}\\ 0& R(l_i,n_j)>I_{\left|x-y\right|}\end{array}\right.,1\le x,y\le 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为：$C_L=C_{l_1}\cap C_{l_2}\cap ...C_{l_i}\cap ...\cap C_{l_m},l_1,l_2,...l_i...,l_m\in L$4)重复步骤3)，为各未分配信道的链路集进行第二轮分配满足无干扰约束条件的部分重叠信道；第二轮分配结束后将多播树中本轮已经分配信道的链路集看成一个无干扰链路集LS₂，从未分配信道的链路集中划去此无干扰链路集；以此类推，对各未分配信道的链路集进行第三、四、……N轮满足无干扰约束条件的部分重叠信道分配，直至多播树中未分配信道的链路集为空集，形成N个无干扰链路集LS₁，LS₂，LS₃，…，LS_N；多播树中所有链路都被分配信道时，多播部分重叠信道分配结束；5)采用静态分时调度的方法调度各无干扰链路集LS₁，LS₂，LS₃，…，LS_N，实现多播树中所有链路的无干扰数据传输。