无线传感网络(wireless sensor network，WSN)综合了传感器技术、嵌入式计算技术、分布式信息处理技术及无线通信技术，是一项能够对网络分布区域内的不同监测对象信息协作地进行实时监测、感知和采集的多元综合性技术．网络中的传感器节点通过无线通信的方式将传感信息发送至基站，再由基站通过有线或无线通信的方式将信息发送给终端用户，在此过程中，无线传感网络的传输调度效果会直接影响网络的服务质量(QoS)，近年来，对WSN传输调度的研究也逐渐变得广泛和热门[1-7]．基于图论中的染色策略[8]，对顶点进行动态染色，通过不同的顶点颜色来确定顶点服务优先级的算法，是现今WSN调度中常用的策略．将图论经典染色算法DVC算法[9]运用在无线传感网络中，WSN的节点类比于DVC算法中的顶点，通过对节点的动态染色，可以确定每个节点的服务优先级次序，便于后续对节点进行处理．节点动态染色过程中，当有信息经过节点时，每个节点会根据自身的信息以及周围的环境信息(相邻节点产生的直接干扰以及相邻节点的节点产生的次生干扰)来计算节点权重，不同的节点权重对应不同的服务优先级并用不同的颜色进行染色标记；当有新的信息加入时，每个节点会重新计算权重，完成对节点的动态染色．对节点实施动态染色处理便于后续对网络的传输调度进行管理．节点的服务优先级确定好后，还须判断是否与当前时隙冲突．在时分复用调度算法GCSA[10]中，若当前时隙已经被占有，则继续选择等待，直至上一任务调度完成，这样的操作会浪费大量时间．若某些服务数据量较大，则分配到的时隙不够．基于公平选择的TSFA[11]会选择先利用当前时隙对服务进行处理，处理不完的服务安排到下面的时隙，节约了传输时间，同时也会造成大量的数据丢包．针对上述问题，本研究提出了一种新的无线传感网络调度方法，即基于动态顶点染色的时隙调度算法(time-step scheduling based on node-dynamic-coloring，TSBN)．将无限传感网络中的动态节点作为图染色中的顶点，通过对节点染色确定不同服务优先级顺序，为不同优先级预留不同时隙，通过对节点的调度完成对时隙的调度，让信息能在网络上快速顺畅的传输，同时对于部分QoS参数如时延、丢包有明显优化效果．最后通过对比实验验证了TSBN算法在网络传输调度过程中的优越性．1 网络模型考虑到图染色和无线传感网络的特点，建立由n个随机部署的传感节点构成的无线传感网络拓扑，若用点集V代表网络中的节点，边集E∈V×V表示节点间的通信链路，可以把网络抽象成G=(V,E)结构，若节点i和j间形成一条路径，则图G中有(i，j)∈E．当一个监测区域内有多个这样的无线自组织网络，就会构成如图1所示的动态网络群，每一个单独的自组织网络最终都会将数据发送到数据汇集点，图中DC为数据中心．10.13245/j.hust.210112.F001图1动态网络群每一个动态网络的内部结构如图2所示，里面布置了大量的传感节点．假设图中节点a，f是和基站节点(base node，BN)通信的一级通信节点，节点b，c，d，e是与节点a建立通信的二级通信节点，节点g，h，i，k是在与节点f建立通信的二级通信节点．节点间的实线表示一跳通信链路以及相关节点间产生的主要冲突关系[12]，虚线表示多跳通信链路以及相关节点间产生的次要冲突关系．10.13245/j.hust.210112.F002图2动态网络内部结构对网络模型提出如下约束条件．a. DC在监测区域的中心位置，并且所有节点只在检测区域内发生动态移动．b. 一级通信节点以优先级的确定顺序及单跳的模式与基站建立通信，而二级通信节点使用基于TDMA的MAC协议及多跳或单跳模式与一级节点进行通信，这样可以从协议上最大程度保证通信效率，并为后文对节点、时隙的处理做好准备．c. 网络中所有节点都具备双向通信的能力，这样可以让每个节点能够及时准确判断周围环境信息(来自周围节点的干扰信息)，并结合自身的信息来计算节点权重．2 算法流程基于上述网络模型，提出一种基于动态节点染色的时隙调度算法(TSBN)．将无限传感网络中的动态节点作为图染色中的顶点，通过对节点染色确定不同服务优先级顺序，为不同优先级预留不同时隙，完成对信息及时合理的调度，避免因节点竞争和冲突关系产生的时延过长、丢包过多和能耗过大的问题．算法流程如图3所示．10.13245/j.hust.210112.F003图3TSBN算法流程图算法须执行各个节点权重信息的计算过程，节点的权重信息是判断节点优先级的重要标准，其具体数值会受到数据量、数据发送接收速率、周围节点干扰等多因素影响．将多个节点组成的群体看作节点种群，由于节点自身受周围两跳节点干扰，在去除干扰的过程中会用到差分进化的思想，因此在计算权重值的过程中会用到经典差分进化算法[13]，具体过程如下．首先定义节点ni处自身产生数据的速率为x(ni) (i=1，2，…，k)，这里的数据是节点监听周围环境产生的，故x(ni)表示单位时间内节点通过监听周围环境所获得的数据量；再定义节点ni处自身接收数据的速率为y(ni)，接收的数据来源是相邻节点发送到ni的数据，但考虑丢包，实际接收的数据量会小于发送的数据量．这样，在不考虑干扰的情况下，可以得到节点ni的数据权重为w(ni)=x(ni)+y(ni)．由于节点自身受到两跳节点的干扰，因此通过差分进化的方式去除干扰，得到新的种群，再来计算新种群下每个节点的数据权重．将差分进化评价机制设定为：x'(ni)=x(ni+2)-x(ni+1)-x(ni);y'(ni)=y(ni+2)-y(ni+1)-y(ni)．产生机制设定为： x''(ni)=max{x(ni),x'(ni)+x(ni)}; y''(ni)=max{y(ni),y'(ni)+y(ni)}．去处干扰后，重新计算节点的数据权重w(ni)=x''(ni)+y''(ni)．以此时的数据权重w(ni)为标准，为确定好不同节点的服务层级做准备．构建网络时，已经将无线传感网络抽象成图G=V,E结构，利用DVC算法对图G进行处理，对图G=V,E中的顶点k进行染色，则Vi表示图G中用第i个颜色的顶点集合，节点集合V的一个划分[V1，V2，…，Vk]则会对应图G的一个k顶点染色，这样就把顶点染色问题转化成了独立集的划分问题，而节点优先级的确定也就变成了独立集优先级的确定．根据上文计算好的数据权重，对独立集的优先级进行判断p(Vi)=∑j∈Viw(j)/Ni，式中：Vi为被染色到第i中颜色的独立集；p(Vi)为独立集Vi的服务优先级(占有时隙的优先级)；w(j)为节点j占有的数据权重；Ni为节点数．考虑到网络是动态移动的，且节点也在动态区域内变化，面对不同的服务需求，节点的服务优先级也会发生变化，当节点的优先级发生变化时，可以通过手动加入调整因数来改变节点的服务优先级，此时的优先级判断为p(Vi)=∑j∈Viw(j)/Ni+R,式中R为一个实数，用来提前或滞后节点的优先级．节点的服务优先级确定好后，还须判断是否与当前时隙冲突．很多的算法如GCSA，若当前时隙已经被占有，则继续选择等待，直至上一任务调度完成，这样的操作会浪费大量时间．TSBN算法遇到时隙冲突情况时会重新计算权重，调度到其他时隙，这样会保证时隙的充分使用和节点的合理调度，节约了传输时间，优化了网络的传输性能．若某些服务数据量较大，则分配到的时隙不够，很多的算法如基于公平选择的TSFA会选择先利用当前时隙对服务进行处理，处理不完的服务安排到下面的时隙，这样的操作是为了节约传输时间，可同样会造成大量的数据丢包．TSBN算法以保证数据传输的准确性为首要任务，当遇到这种情况时，会直接回到重新计算数据权重的环节，让优先级原本靠后的服务现占据这个时隙，这样会尽可能保证一个服务数据传输的完整性和准确性．另外，由于算法的复杂度较低，不会占据过多的网络带宽，因此对传输时间的影响也极低．3 实验与分析为了验证TSBN算法的优越性，通过仿真实验对GCSA及TSFA在吞吐量、时延、能耗方面进行比较．选取Taillard数据集[14]作为传感节点产生的传感信息在Matlab平台上进行仿真实验．设置实验参数：节点数量110个(10×11，以图1为网络模型，网络组中共有10个自组织网络，每个网络内有11个节点)；网络动态限定区域(0，0)~(100，100)m；节点初始能量1 J；每个数据包大小为100 B；数据包生成速率为每个时间间隙0~3包．现以一个自组织网络(图1)为例，运用TSBN算法计算节点的服务优先级p(Vi)时，按照四舍五入的规则，通过改变调整因子R的大小，确定最终的服务层级．得到的节点调度信息表如表1所示．二级通信节点在所属时隙内会发送相应的数据包，如果将调度信息表上的信息放在数据包的包头中，那么就可以让调度信息随着数据包的传输到达一级通信节点，确保算法的正常运行．从表1中可以看出：节点权重大并不一定有较高的服务层级，服务层级的最终判断还会受到节点位置、节点数目等条件的影响．10.13245/j.hust.210112.T001表1节点调度信息表一级通信节点二级通信节点二级节点权重服务层级ab5.824ac3.143ad1.754ae6.724fg3.362fh0.982fi1.923fk3.404在确定了一个自组织网络中不同节点的时隙分配后，对于监测区域内所有无线传感网络都进行TSBN，并且在吞吐量、时延和能耗三个方面对TSFA及GCSA进行对比实验．在实际工业应用中，为保证网络有效性和可靠性的平衡，时隙选取范围不宜过大，一般控制在500以内[15]．考虑实际应用效果，并为了找到TSBN最佳适用区间，隙选取范围为(0，1 000)．实验结果如图4~6所示．10.13245/j.hust.210112.F004图4吞吐量对比10.13245/j.hust.210112.F005图5时延对比10.13245/j.hust.210112.F006图6能耗对比从图4看出：在算法执行的初始阶段，由于TSBN对网络中的流量情况、须传输处理的信息等都不太了解，因此吞吐量和TSFA没有较大差异．当TSBN算法运行一段时间后，一级通信节点能够接收到二级通信节点的调度信息并将信息反馈给网络，让网络按照调度信息对节点进行调度，吞吐量对比TSFA有明显提升，但是当时隙大于960时，TSFA的吞吐量又超过了TSBN，这是因为TSBN预留时隙过多，占据了一定的带宽，从而影响了网络的吞吐量．在实际应用中，应该对时隙的选择范围进行一定的限制，不宜预留较多时隙．从实验结果可以看出：令TSBN吞吐量最优的时隙区间是(400，960)．另外，TSFA和GCSA算法的吞吐量都要多于GCSA，在吞吐量方面都有一定提升．从图5看出：TSBN和TSFA在时延方面也优于GCSA，这是因为两者都在信道利用率方面有很大改善，所以随着时间的增加，在时延性能方面的优势就体现得越明显．另外，由于TSBN采用了基于流量的传输调度策略，时延一开始要多于TSFA，但随着时间增加，TSBN的低时延性能就表现得格外明显，也证明了TSBN在时延性能方面有显著提升．从图6看出：三种算法在实验初期的能量损耗差距很小，可是随着时间的增加，GCSA的能耗明显多于另外两种算法，这是因为其信道利用率较其他两种算法要低得多．另外，由于TSBN与TSFA相比，通信开销小、算法复杂度低，因此随着实验的进行，TSBN能耗较其他两种算法要低很多，TSBN在能量消耗的性能方面有明显的提升．和现有的方法相比，TSBN能让网络的吞吐量最多能提升44.5%，时延最多减少12.5%，能耗最多降低20.8%，有效优化并提升无线传感网络的传输性能．4 结语提出了一种新的无线传感网络调度方法，即基于动态顶点染色的时隙调度算法(TSBN)．将无限传感网络中的动态节点作为图染色中的顶点，通过对节点染色确定不同服务优先级顺序，为不同优先级预留不同时隙，遇到时隙冲突情况时会重新计算权重，调度到其他时隙，从而保证时隙的充分使用和节点的合理调度，节约了传输时间，优化了网络的传输性能．另外，TSBN算法以保证数据传输的准确性为首要任务，当遇到紧急情况时，会直接回到重新计算数据权重的环节，让优先级原本靠后的服务现占据这个时隙，这样会尽可能保证一个服务数据传输的完整性和准确性．由于算法的复杂度较低，不会占据过多的网络带宽，因此对传输时间的影响也是极低的．通过对比试验可知：和现有的方法相比，TSBN能让网络的吞吐量最多提升44.5%，时延最多减少12.5%，能耗最多降低20.8%，有效地优化并提升无线传感网络的传输性能．和其他调度算法相比，该算法增加了网络的吞吐量，降低了网络传输时延，减少了网络的能耗，保障了网络的传输调度过程，提升了网络的整体性能．