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

　　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)改进的顺序着色算法.