基于Multi-Radio Multi-Channel传感器网络无冲突信道分配算法的研究

蔡凤丽，刘新永

(1.安徽电子信息职业技术学院电子信息系，安徽蚌埠230000;2.解放军装甲兵学院信息管理中心，北京100000)

一、MM传感器网络中路由选择标准

此次研究中选择的MM传感器网络应满足以下条件:网络中具有一个Sink节点以及两个及其以上的Sensor节点;任何一个Sensor节点不得超过M个Radio;任何一个Radio中都有N个正交信道;任何一个Radio都能够使用K级的发射功率开展具体的通信，且要满足P1为最小的条件。将Dis(Pi)定义为节点位于功率Pi时的通信半径，E(Pi)代表的是节点在功率为Pi处发送的一个数据包所需要耗费的能量。

(一)最佳选择功率

定义在节点S处可以在某级功率下实现和节点D直接进行通信，功率Pi可以看做是节点S的最佳选择功率。定义Pi满足以下条件:Dis(Pi-1)＜Dis(S，D)≤Dis(Pi)，则登记为 OCP(S，D)=Pi，公式中Dis(P0)=0，Dis(S，D)代表的是节点S与节点D两者之间的物理距离。

(二)相互干扰

在既定的两个链路li=(Si，Di)以及 lj=(Sj，Dj)，其中Si、Sj分别代表的是源节点，Di、Dj指的是目的节点，li在传感网中的通信功率用Pi(1≤i≤K)表示，lj在传感网中的通信功率用Pj(1≤j≤k)表示。那么链路li与lj就可以被定义为相互干扰。只有满足 Dis(Si，Sj)≤Dis(Pi)或者 Dis(Si，Dj)≤Dis(Pi)。Dis(Sj，Si)≤Dis(Pj)、Dis(Sj，Di)≤Dis(Pj)。则对于网络中任何两条链路li、lj，假如两者相互干扰，那么就记做是 MI(li，lj)=1，反之则 MI(li，lj)=0。

二、基于MM传感器网络无冲突信道分配算法介绍

为了最大限度地控制数据通信过程中对于能量的消耗以及控制通信所影响的范围，文中采用建立在最短路径能量基础上的一种MM传感器网络中，无冲突信道分配算法选择时的混合功率路由算法。对于任何一个由R个节点(其中包括一个Sink节点)所构成的MM传感器网络，我们都将其代价矩阵看做是［COSTi，j］R×R。假如在节点 Si处可以实现和节点 Sj进行特定级功率的直接通信，那么就确定为COSTi，j=E(OCP(Si，Sj)); 反之则认为是 COSTi，j=+ ∞.通过上文所规定的代价矩阵，可以推断出一种建立在Dijkstra最短路径前提上的混合功率路由算法。

三、无冲突信道分配上界

(一)冲突信道

就MM传感器网络而言，通过选择HPRA算法最终推算出网络的路由之后，就相当于明确了网络中与之相对应的路由拓扑，即网络的拓扑图(TG)。TG指的是一个将Sink节点看做是根的树。在研究中通过对TG进行进一步的边—点进一步抽象，就可以顺利推出网络中旬在的信道冲突图。完成该步操作只需要两个步骤:首先将位于拓扑图中的任何一条链路li进行抽象，最终将其定义为冲突图中存在的电Ni;其次，针对任何两条链路li以及lj，找到在冲突图中与之相对应的点Ni、Nj，假如满足MI(li，lj)=1，那么可以将Ni以及Nj这两点之间连成一条边。

(二)对基于MM传感器网络无冲突信道分配算法的特性推导

对于任何一个信道冲突图CG来讲，全部有满足条件的 X(CG)≤Δ(CG)+1.成立。在公式中，v(CG)代表的是图CG中存在的最大顶点度。可以推断出，位于这样的链中，所存在的最大长度一定可以用K+1表示。再加上存在于奇圈中的冲突途中一定会包含有奇数个顶点，任何一个顶点都有与之相对应的一条链路，而任何一条链路都能够在拓扑图中找到与之相对应的Sensor节点，那么就推出在奇圈中，应当最多有2K+1个与之相对应的网络节点。一旦网络的Sensor节点规模超过2K+1的数值，那么一定能够推出网络的信道冲突图绝对不会是奇圈，这就能够进一步的证实网络通信半径大于3倍的网络最大功率通信半径的前提下，Sensor节点规模满足2倍网络功率级数加1的环境下，网络无冲突信道分配的信道数达到网络信道冲突图的最大值。

(三)信道分配

通过上述定理的运用，我们设置这样的条件:在满足Sensor节点规模满足2倍网络功率级数加1的环境下，网络无冲突信道分配的信道数达到网络信道冲突图的最大值的这一定理下，笔者决定使用一种满足此次试验要求的信道分配算法，即所说的无冲突信道分配算法，在该种算法中假设网络中一共存在△(CG)个正交信道，与此同时网络符合规定的网络通信半径NCR大于3倍的Dis(PK)，且该网络中的Sensor节点规模超过2K+1。

(四)实验与结果分析

我们假设位于整个网络中存在这么一个，即Sink节点，该节点和数目大于二的Sensor节点相互影响。假如Sensor节点中，其刚开始工作的初始能量确定为1000个单位，那么其就能够在3级功率的条件下开展工作。至于每级的功率x，我们将其通信半径Dis(x)看做是用公式KD与(x-1)两者相乘所得数据之后与BD相加的值，在传输过程中，我们将一个数据包所消耗的能量E(x)定义为KE与x两者之间相乘所得到的的数值，在此次试验中KD值最终与BD相等，同时与KE的值相一致全部等于1，节点要保证顺利接收一个数据包必须消耗一个单位的能量。在实验过程中，假设任何一个节点所拥有的信道数目为△(CG)，任何一个Sensor节点在实际工作中都有与之相对应的1～△ (CG)个Radio以辅助其正常工作。MMH选择通过ZCAA算法实现对信道的科学分配，通过使用HPRA算法实现对路由的选择，SMH网络中保证有数量足够的信道数，操作人员通过使用HPRA算法实现对路由选择。在SSM网络中往往有且只有一个Radio以及一个Channel，可以在最大功率下进行工作，运用最短路径算法对进行路由完成工作，接下来操作人员需要单独使用MMH、SMH和SSM对以上阐述工作中的工作进行表示，并对其开展相应的协议规定和运用。

［1］W H Tam，Y C Tseng.Joint multi-channel link layer and multi-path routing design for wireless mesh networks.Proc of IN-FOCOM，2010，(7).

［2］梁振球，陈 雅.无线传感器网络移动代理路由算法的仿真研究［J］. 计算机仿真，2011，(2).