一种新的传感器网络混合广播调度方法

摘  要：由于传感器网络所使用无线信道的共享性和相互干扰，节点间数据广播会产生资源冲突，广播调度要解决的即是为每个节点分配到一个无冲突传输时隙，其目标是找到晟优时分复用（TDMA：Time division multiple access）调度解，使得帧长度最短而信道利用率最大．提出基于神经网络的两阶段混合广播调度算法．在阶段一，使用改进的顶点着色算法来获得调度所需最短时隙数目；在阶段二，使用模糊Hopfield将节点模糊聚类为M类，同类节点可以在同一时隙被调度，不同类节点必须在不同时隙被调度．用该算法对3个测试拓扑图进行调度，实验结果表明该算法比其他算法能获得更短的帧长度和更低的网络延迟，证明了所提算法的可行性和有效性．

关键词：无线传感器网络；广播调度问题；Hopfield神经网络；图着色

1  引  言

      在监测区域内，以随机方式分布的集成有传感器、数据处理单元和无线通信模块的微小节点通过自组织方式便构成了无线传感器网络（WSN） ^[1] ．WSN中节点经常需要广播消息或数据，用于同步机制、拓扑控制或路由建立与维护等．由于无线链路的共享与开放性，很容易造成消息传输时的相互冲突，若节点的多个相邻节点同时向该节点广播消息，则必然产生相互干扰或冲突并造成广播消息不能正确收发，大多数WSN网络此时要求源节点重传，而造成节点能量额外消耗，从因此需要对节点的消息广播进行合理调度以延长网络寿命^[2] ．大多数WSN使用时分复用（TDMA）作为无线信道共享与接入方式^[3] ,本文研究TDMA下WSN网络广播调度问题（broadcast scheduling problem,BSP），期望能实现在网络拓扑稳定下，节点间消息无冲突传输，并最大化信道利用率．

2  广播调度问题

      记WSN网络为无向简单图G＝（V,E）,顶点V＝｛v_i｝代表网络中传感节点，边E＝｛e_ij｝为节点问传输链路．若传感节点i∈V，j∈V，且i,j在彼此的传感半径内，则称i,j为一跳相邻节点，即存在无线链路eij∈E；若i，j间不存在一跳相邻节点，但存在中间节点k使得e_ik∈E且e_kj∈E，则称节点i，j为二跳相邻节点．传感节点问要能正确收发数据，必须满足以下约束条件[3]:1）节点不能同时接收与发送数据，即若e_ij∈E，则节点i与节点j必须分配以不同时隙来传输数据，称作第1类约束；2）节点不能同时接收两个或多个相邻节点发送的数据，即若e_j∈且e_kj∈E，则节点i,k必须在不同时隙发送数据以避免在节点j处发生冲突，称作第2类约束．定义二进制矩阵S＝｛sij｝表示一个传输调度，ρ为WSN的带宽利用率，用S′＝｛S¹，S²，…｝表示无干扰可行调度集，则最优调度问题描述如下:

      对于给定拓扑WSN网络，寻找最优调度S^opt∈S′,在满足第l类和第2类约束条件下，具有最短的帧长度S^opt和最大的信道带宽利用率ρ^opt．

3  基于神经网络的两阶段调度方法

3.1  阶段

      对给定拓扑的无向图，阶段一目标是使帧时隙长度降为最短，即用最少时隙数M完成调度．图的顶点着色问题（VCP）求解是NP完全的，目前的求解方法主要是启发式算法．虽然顺序着色只能找到次优解,但其复杂度最小。计算量比其他最优和次优算法要低1～2个数量级．考虑到传感节点的能量和计算能力有限，这里结合最大饱和度与最大度数准则设计新的顶点着色算法．

      算法包含如下3个处理环节：1）确定帧时隙长度上下界．对于有N个结点WSN网络，最优帧长度范围为Lm≤M≤N，其中Lm＝maxdegi＋1,degi为节点i的度数；2）执行初始化时隙分配．令待初始化节点集合为G＝｛n_i,i=1,2,…,L_m｝,G由图中具有最大度数的节点n₁及与n₁相距l跳节点的相邻节点n_i构成，将时隙i分配给节点n_i；3）改进的顺序着色算法．

      算法

      输入：原始WSN拓扑G＝（V,E）.

      输出：节点时隙调度矩阵S=｛S_ij｝_N×M.

      Step1  网络节点拓扑排序．对节点按照度数递减规律排序并存储为队列Q=｛ni,i＝1,2,…，N｝，得到网络节点的最大度数△G；

      Step2  确定时隙下确界．置初始时隙数M＝△G十1，调度矩阵S＝｛0｝_N×M；

      Step3  节点时隙初始化调度．不失一般性，将第i个时隙分配到节点n_i，得已调度节点集Gc＝｛n_i,i＝1,2,…，M｝,令S_ii=1,计数器P＝M＋1；

      Step4  对未调度节点排序．按照最大饱和度准则对剩下的N-L_m个顶点排序，存储为队列

      Step5  调度Q′中节点n_j．搜索满足2跳内约束的时隙，记不同时隙数为Nc，依据Nc值分别执行以下处理：

      ①若N_c＞1,将第一个可用时隙指派给节点n_j，Sij=1；

      ②若N_c＝1,将该唯一时隙指派给节点n_j，S_ij=1；

      ③若N_c＝0,则此时无空闲时隙指派给节点n_j，转Step7；

      Step6  判断是否所有节点已完成调度．若P＝N，算法停止；否则令P=P＋1，转Step5；

      Step7  新增一个时隙，重新调度．令M＝M＋1，转Step5．

      算法Step1排序的计算量为O（|N|）,Step4排序的计算量为O（|N-Lm|³）,N为网络顶点数，Lm是顶点最大度数加1,整个算法的计算量约为O（|N|³）

3.2  阶段二

      在阶段二，使用模糊Hopfield神经网络对WSN网络节点进行模糊聚类^[4、5] ，分类数为阶段一中求得的M，输入样本为待调度节点．同一类中的所有节点可以在同一个时隙同时被调度；不同类中的节点必须在不同时隙被调度．考虑N×M结构Hopfield网络，节点i是否在第j个时隙传输数据由Hopfield处在（i,j）位置神经元的输出Pij确定．利用第2节中的约束条件来设计优化目标，即Hopfield网络能量函数E．首先，所有的数据包应该在一个时隙内同步传送；其次，当节点i时隙j传输数据时，其他所有节点i的相邻节点不能分配在时隙j；最后，当节点i传输数据时，i的二跳相邻节点也不能被分配到时隙j去传输数据．能量函数E大小反映网络当前时隙调度与最优调度间差距，在考虑所有以上约束条件后，本文所设计能量函数E如下：

      其中：n_i表示第i个节点，d_ij为节点i，j间欧氏距离，权值w₁和w₂为正且满足w1+w2＝l,权系数取值会影响网络收敛性，需合理选取．V_i为第i类欧氏中心，即．（i,j）位置神经元输入为I_ij＝（n_i-v_i）²＋△I_ij，神经元输出为P_ij，外部激励项△I_ij取常数．Hopfield网络优化流程如下：

      Step1  初始化网络内神经元（i,j）输出P_ij:

      Step2  更新模糊隶属度函数，重新计算类中心v_i；

      Step3  由式（1）计算能量函数；

      Step4  判断网络是否收敛于稳定状态，若|E（n+1）-E（n）|〉ε（ε为阈值），转Step2；否则，网络收敛，算法终止．

4  实验结果与分析

      对TS-HNN算法的调度性能进行分析，与平均退火策略（MFA） ^[2] 、基于遗传算法的Hopfield神经网络（HNN-GA） [^4]和含噪混沌神经网络（NC-NN） ^[5]3种方法调度性能比较．使用3种不同拓扑的测试网络Case 1～3^[6] .实验中使用的数据包为固定长度，时隙长度设置为每包所需传输时间；节点问以泊松分布随机收发数据包．每种拓扑结构运行50次，取平均值进行比较．表1给出本文算法（TS-HNN）与其他3种方法求解得到的网络最小延迟η和帧长度M．在节点数较少（Case 1）或平均度数不高时（Case 3），4种算法都能找到最优帧长M＝8；对于节点数较多具有复杂结构网络（Case 2），TS-HNN也能找到次优帧长；且TS-HNN在3种拓扑下都具有最低的网络时延．测试拓扑Case 1调度结果如图l所示，填充有黑色的方格代表所在节点（node）在该时隙（slot）可被调度．图2详细描述了网络时延随数据包（packets）服务速率变化的情况．随着服务速率增加，网络时延也在变长，在节点数较少时（Case 1），4种算法的时延相差不大，如图2（a）；当节点数增加时（Case 2）,4种算法下的网络时延差异明显增大，如图2（b）．

5  结束语

      调度是一类经典的带约束资源优化分配问题本文以传感器网络为研究背景，提出了一种基于图着色与神经网络的两阶段广播调度算法．算法的基本思想是将广播调度问题求解转化为两阶段目标寻优：第1阶段借助顶点着色思想搜索给定拓扑WSN的具有最短时隙数目的帧结构；第2阶段在上述帧结构下使用模糊Hopfield网络为每个节点增添额外的无冲突传输时隙，从而使得在原有帧长度下尽可能多的让更多节点实现并行无干扰传输，以最大化信道利用率，仿真实验证明了所提方法的有效性．

参考文献：

[1]PENG Y,SOONG B H,WANG L.Broadcast scheduling in packet radio networks using mixed tabu-greedy algorithm[J].Electronics letters,2004,40（6）:375-376.

[2]WANG G,ARISARIN.Optimal broadcast scheduling in packet radio networks using mean gield annealing[J].IEEE Journal on Selected Areas in Communications.1997,15（2）:250-260.

[3]YEO J,LEE H.An efficient broadcast scheduling algorithm for tdmad-hoc networks[J].Computer Operations Research,2002,29（13）:1793-1806.
详情请点击：一种新的传感器网络混合广播调度方法