由于传感器网络所使用无线信道的共享性和相互干扰，节点间数据广播会产生资源冲突，广播调度要解决的即是为每个节点分配到一个无冲突传输时隙，其目标是找到晟优时分复用（TDMA：Time division multiple access）调度解，使得帧长度最短而信道利用率最大．提出基于神经网络的两阶段混合广播调度算法．在阶段一，使用改进的顶点着色算法来获得调度所需最短时隙数目；在阶段二，使用模糊Hopfield将节点模糊聚类为M类，同类节点可以在同一时隙被调度，不同类节点必须在不同时隙被调度．用该算法对3个测试拓扑图进行调度，实验结果表明该算法比其他算法能获得更短的帧长度和更低的网络延迟，证明了所提算法的可行性和有效性．
1 引 言
在监测区域内，以随机方式分布的集成有传感器、数据处理单元和无线通信模块的微小节点通过自组织方式便构成了无线传感器网络（WSN） [1] ．WSN 中节点经常需要广播消息或数据，用于同步机制、拓扑控制或路由建立与维护等．由于无线链路的共享与开放性，很容易造成消息传输时的相互冲突，若节点的多个相邻节点同时向该节点广播消息，则必然产生相互干扰或冲突并造成广播消息不能正确收发，大多数WSN网络此时要求源节点重传，而造成节点能量额外消耗，从因此需要对节点的消息广播进行合理调度以延长网络寿命[2] ．大多数WSN使用时分复用（TDMA）作为无线信道共享与接入方式[3] ,本文研究TDMA下WSN网络广播调度问题（broadcast scheduling problem,BSP），期望能实现在网络拓扑稳定下，节点间消息无冲突传输，并最大化信道利用率．
2 广播调度问题
记WSN网络为无向简单图G＝（V,E）,顶点V＝｛vi｝代表网络中传感节点，边E＝｛eij｝为节点问传输链路．若传感节点i∈V，j∈V，且i,j在彼此的传感半径内，则称i,j为一跳相邻节点，即存在无线链路eij∈E；若i，j间不存在一跳相邻节点，但存在中间节点k使得eik∈E且ekj∈E，则称节点i，j为二跳相邻节点．传感节点问要能正确收发数据，必须满足以下约束条件[3]:1）节点不能同时接收与发送数据，即若eij∈E，则节点i与节点j必须分配以不同时隙来传输数据，称作第1类约束；2）节点不能同时接收两个或多个相邻节点发送的数据，即若ej∈且ekj∈E，则节点i,k必须在不同时隙发送数据以避免在节点j处发生冲突，称作第2类约束．定义二进制矩阵S＝｛sij｝表示一个传输调度，ρ为WSN的带宽利用率，用S′＝｛S1，S2，…｝表示无干扰可行调度集，则最优调度问题描述如下:
对于给定拓扑WSN网络，寻找最优调度Sopt∈S′,在满足第l类和第2类约束条件下，具有最短的帧长度Sopt和最大的信道带宽利用率ρopt．
3 基于神经网络的两阶段调度方法
3.1 阶段
对给定拓扑的无向图，阶段一目标是使帧时隙长度降为最短，即用最少时隙数M完成调度．图的顶点着色问题（VCP）求解是NP完全的，目前的求解方法主要是启发式算法．虽然顺序着色只能找到次优解,但其复杂度最小。计算量比其他最优和次优算法要低1～2个数量级．考虑到传感节点的能量和计算能力有限，这里结合最大饱和度与最大度数准则设计新的顶点着色算法．
算法包含如下3个处理环节：1）确定帧时隙长度上下界．对于有N个结点WSN网络，最优帧长度范围为Lm≤M≤N，其中Lm＝maxdegi＋1,degi为节点i的度数；2）执行初始化时隙分配．令待初始化节点集合为G＝｛ni,i=1,2,…,Lm｝,G由图中具有最大度数的节点n1及与n1相距l跳节点的相邻节点ni构成，将时隙i分配给节点ni；3）改进的顺序着色算法．
算法
输入：原始WSN拓扑G＝（V,E）.
输出：节点时隙调度矩阵S=｛Sij｝N×M.
Step1 网络节点拓扑排序．对节点按照度数递减规律排序并存储为队列Q=｛ni,i＝1,2,…，N｝，得到网络节点的最大度数△G；
Step2 确定时隙下确界．置初始时隙数M＝△G十1，调度矩阵S＝｛0｝N×M；
Step3 节点时隙初始化调度．不失一般性，将第i个时隙分配到节点ni，得已调度节点集Gc＝｛ni,i＝1,2,…，M｝,令Sii=1,计数器P＝M＋1；
Step4 对未调度节点排序．按照最大饱和度准则对剩下的N-Lm个顶点排序，存储为队列
Step5 调度Q′中节点nj．搜索满足2跳内约束的时隙，记不同时隙数为Nc，依据Nc值分别执行以下处理：
①若Nc＞1,将第一个可用时隙指派给节点nj，Sij=1；
②若Nc＝1,将该唯一时隙指派给节点nj，Sij=1；
③若Nc＝0,则此时无空闲时隙指派给节点nj，转Step7；
Step6 判断是否所有节点已完成调度．若P＝N，算法停止；否则令P=P＋1，转Step5；
Step7 新增一个时隙，重新调度．令M＝M＋1，转Step5．
上一篇：指纹传感器的工作原理及应用
