一种用于多信道无线传感器网络的信道分配方法

摘要

本发明公开了一种用于多信道无线传感器网络的信道分配方法，该方法包括如下步骤：（1）根据多信道无线传感器网络拓扑图G，获得网络链路冲突图CG；（2）根据步骤（1）中获得的网络链路冲突图CG，获得上述网络的极大独立集序列I；（3）根据上述网络拓扑图G，获得上述极大独立集序列I中各个极大独立集的权重；（4）根据各个极大独立集的权重，依次给每个极大独立集对应的链路分配信道。本发明将信道分配给多信道无线传感器网络的各条链路，使得网络中的链路可以工作在不同的信道上。

主权项

一种用于多信道无线传感器网络的信道分配方法，其特征在于：该方法包括如下步骤：(1)根据多信道无线传感器网络拓扑图G，获得网络链路冲突图CG；(2)根据步骤(1)中获得的网络链路冲突图CG，获得上述网络的极大独立集序列I；(3)根据上述网络拓扑图G，获得上述极大独立集序列I中各个极大独立集的权重，假设网络拓扑图G中各个顶点记为v₁，v₂，v₃，…，v_N，其中，顶点v_p，v_q之间的边记为顶点v_p和v_q距离汇聚顶点的最短跳数分别记为H(v_p)和H(v_q)，极大独立集序列I中各个极大独立集的权重通过以下方式得到：(a)根据网络拓扑图G中各个顶点v₁，v₂，v₃，…，v_N距离汇聚顶点的最短跳数，获得网络拓扑图G中各条边距离汇聚顶点的跳数，边距离汇聚顶点的最短跳数$H\left(e_{v_p,v_q}\right)=\frac{1}{2}[H\left(v_p\right)+H\left(v_q\right)];$(b)根据网络拓扑图G中各条边距离汇聚顶点的跳数，网络链路冲突图CG中各条边的权重，边的权重$w(e_{v_p,v_q},e_{v_m,v_n})=1-\frac{H\left(e_{v_p,v_q}\right)+H\left(e_{v_m,v_n}\right)}{\mathrm{Max}[H\left(e_{v_m,v_n}\right)+H\left(e_{v_m,v_n}\right)]+1},$其中$\mathrm{Max}[H\left(e_{v_m,v_n}\right)+H\left(e_{v_m,v_n}\right)]$表示距离汇聚节点跳数最大的边的跳数和；再根据网络链路冲突图CG中各条边的权重，得到网络链路冲突图CG中每个顶点的权重；(c)根据上述网络链路冲突图CG中各个顶点的权重，得到各个极大独立集的权重；(4)根据各个极大独立集的权重，依次给每个极大独立集对应的链路分配信道，包括如下的步骤：(a)初始化，设待分配顶点集合A为网络链路冲突图CG中所有顶点，已分配顶点集合B为空集，已分配顶点集合中顶点间的总冲突值M为0，可使用信道集合为{1，2，…，K}，计数值i＝1；(b)将极大独立集序列I中各个极大独立集按照权重从大到小排列；(c)将极大独立集序列I中第i个极大独立集中的顶点加入已分配顶点集合B，并从待分配顶点集合A中删除；(d)分别计算出给第i个极大独立集分配信道j时，1≤j≤K，已分配顶点集合中顶点间的总冲突值M，M即为集合B中所有顶点间边的权重和，取使得已分配顶点集合B中所有顶点间边的权重和M最小的信道k分配给第i个极大独立集中的顶点；(e)判断待分配顶点集合A是否为空集，如果判断结果为否，则i＝i+1，返回步骤(c)；如果判断结果为是，则停止计算，得到每个网络拓扑图G中的链路分配信道。