2018基于CPN的WBANs调度算法研究

8319988

　　【摘 要】将无线体域网间调度问题(Inter-WBANs Scheduling，IWS)转化为基于中央处理节点(Central Process Node，CPN)的调度，模型化为图着色问题。提出一种启发式混合遗传模拟退火算法对相应的WBAN进行调度，缓解网间干扰，使无线体域网的整体性能得到优化。另外，本文基于仿真结果对算法进行了评估，实验结果表明该算法可以在动态WBAN干扰环境下更好地适用于功耗和资源受限的WBAN。
　　【关键词】无线体域网 体域网间调度 图着色 混合遗传
　　1 引言
　　无线体域网(WBAN)是一种无线个人传感网，主要由1组无线传感器节点及1个中央处理节点(CPN)组成，具体如图1所示。其中CPN主要负责收集来自WSNs的重要数据。与传统无线传感网(WSN)不同，WBAN用户的移动使得对应网络具有较高的移动性[1]，网络拓扑结构和WSN相比也不够稳定。多个WBAN的动态拓扑结构与MANETs相似，但是WBAN是基于组而不是基于节点的动态拓扑。当区域中多个WBAN共存时，各个网络之间相互冲突的可能性极大，因此WBAN间调度研究就显得极为重要。
　　无线体域网的分布式冲突避免调度可以模型化为已知的分布式图着色问题(常用于WSN、MANETs[2])。相应的网络拓扑对应于图模型G=(V，E)。其中V表示传感器节点，E表示相互干扰的2个节点之间无线资源的冲突，颜色集C表示不同的资源单元(时隙、频带或者编码序列)。图G的顶点完全k着色对应，其中|C|=k。这样相邻节点所获得的颜色不同，相应的邻接点获得的资源不同，避免网络之间的冲突。
　　本文通过将WBANs调度模型化为图着色，提出一种启发式混合模拟退火遗传算法。该算法克服了遗传算法易陷入局部最优、模拟退火算法收敛较慢等缺点，以解决无线体域网调度问题。
　　2 基于CPN的WBAN调度模型分析
　　根据WBAN简单星型网络结构[3]中CPN/WSN的不对等关系，我们将WBAN调度模型简化为对WBAN中CPN节点的调度。单个WBAN中，CPN作为主节点，其他WSNs为其附属节点，CPN对WSNs的加入、离开以及资源分配进行管理。基于此，本文假设了1种基于CPN的2步IWS，具体如图2所示：
　　图2 基于CPN的WBAN调度模型
　　CPN首先与干扰范围内的其他CPNs进行资源协商，然后将占有资源向其WSNs进行分配。这样，当从对应的CPN接收到带有预先设定的传输模式的信标信息并遵循该模式向CPN发送重要信号时，WSNs被唤醒。
　　为模拟WBANs网络，随机构造1个2维图G=(V，E)。V(G)表示CPN集，E(G)表示CPN之间冲突链集。在一个区域内随机布置n=|V(G)|个顶点，用来模拟WBAN用户所处的随机空间位置。如果CPNs之间的距离等于或略小于WBAN之间的相互干扰范围，用边连接对应顶点。在这种情况下，基于CPN的IWS与MANET调度类似，但是两者对资源的调度策略不同。MANET中，每个顶点代表1个无线节点，MANET注重有效的内节点通信与路由。因此可以采用边着色，对应于节点与节点之间的通信调度，而在基于CPN的IWS中，每个顶点代表1个传感器组。基于CPN的IWS试图解决属于不同用户的传感器组之间的冲突问题。因此顶点着色对应于动态基于CPN的传感器组调度问题是合适的。这样基于CPN的IWS，1个随机图的k着色[4]可以对应于，其中|C|=k，邻接顶点就获得完全不同的颜色，相应地表示相关数据传输的不同资源单元(从WSNs到CPN)。着色算法执行1次，完成1次k种资源映射。
　　3 启发式模拟退火遗传算法解决图着色
　　问题
　　简单的模拟退火遗传算法[5]结合了全局寻优与局部寻优性能，相对于单独的模拟退火算法或者遗传算法，其计算效率较高。因此在模拟退火遗传算法基础上添加启发式搜索，更有助于算法性能的提高。
　　3.1 启发式搜索算法
　　作为启发式算法的一种，贪婪算法采用贪婪准则逐步构造最优解。即在问题求解的每一个阶段，作出在一定标准下可能的最优决策。就图的顶点k着色来说，贪婪算法在进行着色时，会受限于染色体中顶点的次序，只能根据当前已经被着色的顶点和将被着色顶点的邻接信息来决定本着色顶点的颜色，而不能从全局出发，利用顶点间的关系构造最优着色。本文试图在已获得次优解的邻域内搜索1个更好的次优解，不断进行邻域搜索直到找到局部最优解。
　　3.2 启发式混合模拟退火遗传算法
　　在贪婪启发式遗传算法的框架下增加模拟退火算子，结合3种算法思想的优点，提出新的混合模拟退火遗传算法。
　　3.2.1 模拟退火算子设计
　　根据模拟退火算法思想[6]，本文设计的模拟退火算子如下所示：
　　1 输入：初始解S0，邻接矩阵A
　　2 输出：优化解S1
　　3 Begin
　　4 t=tfEvaluation(S0)tp;//计算初始温度t
　　5 Do
　　6 Do
　　7 n=Neighbor(S0)Sf;//重新计算搜索次数
　　8 随机从S0的邻域中选择一个染色体作为S1
　　9 =Evaluation(S0)-Evaluation(S1)
　　10 if(0)
　　11 Then S0=S1;
　　12 Else按照概率接受新的染色体S1;
　　13 While(循环次数　　14 t=t;//为降温系数
　　15 While(不满足终止条件)
　　16 Return S0;
　　17 End //其中tf、tp、Sf、为用户自定义参数，控制冷却调度
　　另外，算法在每次遗传算法结束获得子代个体后，立即对子代个体执行模拟退火算子。其目的是：
　　1)在全体可行解空间的子集内进行搜索，以期望获得比原来更好的优化解。
　　2)与GGA(贪婪遗传算法)中只允许解质量的提高不同，必要时也允许解质量下降。以一定概率接受恶化解，扩大搜索范围，以期望能够跳过局部最优陷阱，尽可能克服早熟与欺骗现象。
　　3.2.2 启发式遗传算法
　　(1)建立染色体子空间
　　对于简单图G(n)，顶点集V(G)={v1，v2，vn}，边集E(G)={e1，e2，en}。邻接矩阵A(G)=(aij)nn，矩阵A取值如下(n为G中顶点数)：