吕立新
摘要：该文在多Sink节点并行的网络结构基础上，基于能量熵理论建立了多Sink节点任务分配控制模型，设计了基于蚁群算法的任务分配控制策略，该方法能够根据Sink节点的当前状态、能耗情况合理分配数据通信和处理任务，均衡各Sink节点的负载，提高网络数据处理效率和网络生存时间。
关键词： 无线传感器网络； 并行Sink节点； 蚁群算法； 任务分配
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）14-3363-03
Abstract：Parallel Sink node of the network structure is presented in this paper， based on the entropy theory is established based on energy Sink node task assignment control model， design the task assignment control strategy based on ant colony algorithm， this method can according to the current state of the Sink node， the energy consumption situation and reasonable distribution of data communication and processing tasks， and balance the load of each Sink node， improve the efficiency of network data processing and network survival time.
Key words：Wireless Sensor Network； Parallel Sink； Ant colony Algorithm； Task Allocation
将大量传感器节点部署于监测区域，进行实时的数据采集、存储和传输是无线传感器网络的重要应用。传统的无线传感器监测网络采用单一的Sink节点进行网络管理和数据传输，这必然导致Sink节点的计算能耗和通信能耗过高，从而导致Sink节点的能量很快耗尽，缩短了网络生存时间，同时还限制了整个网络通信带宽。利用多Sink节点建立并行的计算网络是解决这一问题的有效方法。在多Sink节点的传感器网络中，各Sink节点地位平等，组成的对等的计算网络，并行完成传感器网络的数据采集、存储、传输等各项任务，均衡网络负载，提高网络生存时间。在多Sink节点并行的无线传感器网络中，设计一种合理的任务分配策略，根据各Sink节点的计算能力、能耗情况，实时合理地分配各项任务，是应用多Sink节点必须要解决的关键问题。文献[1，2]分别使用了遗传算法，模拟退火算法等智能算法，对传统单一Sink节点的传感器网络进行任务分配。但这些方法并不适用于多Sink节点并行多传感器策略。
针对这一问题，该文在多Sink节点并行的网络结构基础上，提出了一种基于蚁群算法的任务分配控制策略，该方法能够根据Sink节点的当前状态、能耗情况合理分配数据通信和处理任务，均衡各Sink节点的负载，提高网络数据处理效率和网络生存时间。
1 多Sink节点任务分配模型
在多Sink节点并行的传感器网络中，采用任务分配控制策略的目的是根据各Sink节点的当前状态，合理分配任务 ，均衡网络负载，降低全网能耗，因而可以用任务执行时间和网络生存时间两个指标来评价任务分配策略的优劣。
一般情况下，网络中任务的执行时间由数据访问时间、数据传输时间和处理时间组成。设数据传输时间为[tt]，其与数据传输总量[Qt]及传输带宽[B]满足式（1）的关系。
[tt=QtB] （1）
设网络中总的数据访问量为[Qa]，数据的读取和写入采用相同的速度，则访问时间[ta]与数据访问量及读写速度[V]满足式（2）所示的关系。
[ta=2QaV] （2）
节点的数据处理时间与节点的CPU类型、内存数量及当前状态下的CPU占用率相关。可以通过实验，在不同的工作状态下统计出节点的处理时间，从而获取一个处理时间的预测值[tp]。网络中任务的执行时间[T]，由各Sink节点中任务耗时最大的值决定，其满足式（3）所示的关系。
[T=max1 设[Tref]为可接受的任务执行时间参考量，则对于某Sink节点[Si]的执行时间评价指标可描述为： [?t（si）=TTref] （4） 无线传感器网络在工作时的能耗主要包括处理能耗、数据通信能耗和数据访问能耗，其中数据通信能耗在节点工作能耗中占的比例最大，为了简化模型本文对处理能耗和访问能耗做忽略处理。设在标准距离[d0]下，节点的最小传输能耗为[P0，t]，Sink节点[Si]与[Sj]的通信距离为[di，j]，则通信能耗可描述为： [Pi，t=d2i，jd20×（4π）2βGtGrλ2×P0，t] （5） 其中[Gt]为Sink节点的无线通信发射系数，[Gr]为接收系数，[λ]为通信波长，[β]为功耗因子。网络的生存时间与节点的剩余能量均衡程序密切相关，节点的剩余能量分布越均衡，网络生存时间越长。假设在[t]时刻， Sink节点[Si]的能量为[Eit]，根据能量熵理论，节点的能量满足式（6）所示的关系。 [I（Si）=log（1P（Eit））=-log（P（Eit））] （8） 网络中所有节点的剩余能量平均度，可定义为：
[H（s'）=-kt∈siP（Eit）logP（Eit）] （9）
其中[H（s'）]为剩余能量熵，其值越大表示节点的剩余能量越平均，网络生存时间越长。由于式（5）中的[（4π）2β/（GtGrλ2）×P0，t]为常量，因而Sink节点[Si]的能耗评价指标可定义为：
[?cost（Si）=-d2i，jd20×H（S'i）] （10）
本文使用包含任务执行时间和网络生存时间二个分项指标的综合评价指标来衡量任务分配控制策略的优劣，使用一个比例调节系数[α（0<α<1）]来控制两个分项指标对综合评价指标的影响程度。综合评价指标[M]可定义为：
[M=α×max（?t（Si））+（1-α）×i=1n?cost（Si）] （11）
2 基于量子蚁群算法的任务分配控制策略
多Sink节点下的任务分配方案属于NP类组合优化问题，可行解的规模随Sink节点的增加将呈几何倍数据增长，由于任务分配必须具有实时性，能随时响应网络的变化，因此本文引入蚁群智能算法来解决这一问题。量子蚁群算法是对传统蚁群算法的一种改进，它采用一组量子比特概率幅值来表示蚂蚁的当前位置，用量子旋转门来实现蚂蚁的移动，用量子旋转门角度的更新实现信息素的增量。这种改进，增加了种群的多样性，避免了传统蚁群算法容易出现过早收敛的缺陷。
在[t]时刻，传感器网络中当前的任务总数为[N]，Sink节点的数量为[R]，蚁群规模为[m]，蚁群集合记为[Ω=X1，X2，…Xm]，蚁群初始化时各蚂蚁按式（12）所示的量子概率幅值选择处于某个Sink节点，其接受任务的数量按式（13）给出的概率随机选择。
[Xk=cosθk1sinθk1cosθk2sinθk2……cosθkRsinθkR] （12）
其中[θij=2π×rnd]，[rnd]为（0，1）间的随机数
[Pk（i，n）=τ（i，n）αη（i，n）βn?Jk（n）τ（i，n）αη（i，n）β0，n∈Jk（n），n?Jk（n）] （13）
其中[α]，[β]为常量，[τ（i，n）]为各Sink节点的任务选择信息素痕迹，[Pk（i，n）（1 [η（i，n）=1/M（i，n）=1/（α×（?t（i））+（1-α）×（?cost（i）））] （14） 蚂蚁K选择完当前Sink节点的任务数后，由位置[Xr]移动到位置[Xk]的规则如式（15）所示，概率随机选择下一个Sink节点的概率如式（16）所示。 [Xs=argmaxxs∈Xτ（Xs）αη（Xs）β] （15） [P（s）=ρss?gk（n）ρs，s?gk（n）0，s∈gk（n）] （16） 其中[P（s）]为Sink节点被选择的概率，[ρs]为一选择常数，[gk（n）]中记录了蚂蚁K已经选择过的Sink节点。信息素根据式（17）进行更新，增加的信息素按公式（18）计算。 [τ（i，n）new=ρτ（i，n）old+k∈ΩΔτ（i，n）k] （17） [Δτ（i，n）k=QMk，select0，not] （18） 量子旋转门和变异处理按文献[5]中的方法进行，进行多代进化计算后，各Sink节点上对应的信息素浓度最大的任务数量即为最优的任务分配方案。 3 实验数据 为了验证任务分配策略的有效性，在OMNet++4.1仿真软件基于Castalia传感器节点模型创建传感器节点，在监测区域部署120个传感器节点，分别使用2～25个并行Sink节点的不同Sink节点数量下进行了任务执行时间和通信能耗的仿真，同时在相同的节点数和任务数下与使用单一Sink节点的网络在任务耗时和通信能耗二个指标下做了对比实验，实验结果如图1和图2所示。 从实验结果可见，基于量子蚁群算法的任务分配控制策略，能较好地根据Sink节点的当前状态合理有效的分配任务，并行完成数据的处理、传送任务，相对于使用单一Sink节点的传感器网络提高了任务执行效率，降低了节点能耗，同时能获取更大的网络生存时间。 4 结束语 针对使用单一Sink节点的无线传感器网络存在任务执行效率低，能耗大能缺点，该文提出了一种多Sink并行的传感器网络结构，通过多Sink节点的并行处理来提高任务处理效率。在此基础上设计了一种基于量子蚁群算法的多Sink节点任务分配控制策略，实验证明该方法能根据Sink节点的工作状态分配任务，均衡各Sink节点的负载，减少任务执行时间和通信能耗，增加了网络生存时间。 参考文献： [1] HONG C， KUMAR S P. Sensor networks： evolution， opportunities，and challenges[J]. Proceedings of the IEEE，2013，91（8）：1247-1256. [2] Krishnamachari L， ESTRIN D， WICKER S. Impact of data aggregation in wireless sensor networks[C]// Proc of Int Workshop of Distributed Event Based Systems. Los Alamitos： IEEE Computer Press，2012：1-11. [3] 刘强，毛玉明，冷甦鹏，等.无线传感器网络中多sink节点优化部署方法[J]计算机应用，2011（9）. [4] 徐久强，柏大治，罗玎玎，等.遗传算法在WSNs多Sink节点布局中的应用[J].东北大学学报：自然科学版，2008（6）. [5] 任秀丽，梁红伟，汪宇.基于多路径蚁群算法的无线传感器网络的路由[J].计算机科学，2009（4）.
[H（s'）=-kt∈siP（Eit）logP（Eit）] （9）
其中[H（s'）]为剩余能量熵，其值越大表示节点的剩余能量越平均，网络生存时间越长。由于式（5）中的[（4π）2β/（GtGrλ2）×P0，t]为常量，因而Sink节点[Si]的能耗评价指标可定义为：
[?cost（Si）=-d2i，jd20×H（S'i）] （10）
本文使用包含任务执行时间和网络生存时间二个分项指标的综合评价指标来衡量任务分配控制策略的优劣，使用一个比例调节系数[α（0<α<1）]来控制两个分项指标对综合评价指标的影响程度。综合评价指标[M]可定义为：
[M=α×max（?t（Si））+（1-α）×i=1n?cost（Si）] （11）
2 基于量子蚁群算法的任务分配控制策略
多Sink节点下的任务分配方案属于NP类组合优化问题，可行解的规模随Sink节点的增加将呈几何倍数据增长，由于任务分配必须具有实时性，能随时响应网络的变化，因此本文引入蚁群智能算法来解决这一问题。量子蚁群算法是对传统蚁群算法的一种改进，它采用一组量子比特概率幅值来表示蚂蚁的当前位置，用量子旋转门来实现蚂蚁的移动，用量子旋转门角度的更新实现信息素的增量。这种改进，增加了种群的多样性，避免了传统蚁群算法容易出现过早收敛的缺陷。
在[t]时刻，传感器网络中当前的任务总数为[N]，Sink节点的数量为[R]，蚁群规模为[m]，蚁群集合记为[Ω=X1，X2，…Xm]，蚁群初始化时各蚂蚁按式（12）所示的量子概率幅值选择处于某个Sink节点，其接受任务的数量按式（13）给出的概率随机选择。
[Xk=cosθk1sinθk1cosθk2sinθk2……cosθkRsinθkR] （12）
其中[θij=2π×rnd]，[rnd]为（0，1）间的随机数
[Pk（i，n）=τ（i，n）αη（i，n）βn?Jk（n）τ（i，n）αη（i，n）β0，n∈Jk（n），n?Jk（n）] （13）
其中[α]，[β]为常量，[τ（i，n）]为各Sink节点的任务选择信息素痕迹，[Pk（i，n）（1 [η（i，n）=1/M（i，n）=1/（α×（?t（i））+（1-α）×（?cost（i）））] （14） 蚂蚁K选择完当前Sink节点的任务数后，由位置[Xr]移动到位置[Xk]的规则如式（15）所示，概率随机选择下一个Sink节点的概率如式（16）所示。 [Xs=argmaxxs∈Xτ（Xs）αη（Xs）β] （15） [P（s）=ρss?gk（n）ρs，s?gk（n）0，s∈gk（n）] （16） 其中[P（s）]为Sink节点被选择的概率，[ρs]为一选择常数，[gk（n）]中记录了蚂蚁K已经选择过的Sink节点。信息素根据式（17）进行更新，增加的信息素按公式（18）计算。 [τ（i，n）new=ρτ（i，n）old+k∈ΩΔτ（i，n）k] （17） [Δτ（i，n）k=QMk，select0，not] （18） 量子旋转门和变异处理按文献[5]中的方法进行，进行多代进化计算后，各Sink节点上对应的信息素浓度最大的任务数量即为最优的任务分配方案。 3 实验数据 为了验证任务分配策略的有效性，在OMNet++4.1仿真软件基于Castalia传感器节点模型创建传感器节点，在监测区域部署120个传感器节点，分别使用2～25个并行Sink节点的不同Sink节点数量下进行了任务执行时间和通信能耗的仿真，同时在相同的节点数和任务数下与使用单一Sink节点的网络在任务耗时和通信能耗二个指标下做了对比实验，实验结果如图1和图2所示。 从实验结果可见，基于量子蚁群算法的任务分配控制策略，能较好地根据Sink节点的当前状态合理有效的分配任务，并行完成数据的处理、传送任务，相对于使用单一Sink节点的传感器网络提高了任务执行效率，降低了节点能耗，同时能获取更大的网络生存时间。 4 结束语 针对使用单一Sink节点的无线传感器网络存在任务执行效率低，能耗大能缺点，该文提出了一种多Sink并行的传感器网络结构，通过多Sink节点的并行处理来提高任务处理效率。在此基础上设计了一种基于量子蚁群算法的多Sink节点任务分配控制策略，实验证明该方法能根据Sink节点的工作状态分配任务，均衡各Sink节点的负载，减少任务执行时间和通信能耗，增加了网络生存时间。 参考文献： [1] HONG C， KUMAR S P. Sensor networks： evolution， opportunities，and challenges[J]. Proceedings of the IEEE，2013，91（8）：1247-1256. [2] Krishnamachari L， ESTRIN D， WICKER S. Impact of data aggregation in wireless sensor networks[C]// Proc of Int Workshop of Distributed Event Based Systems. Los Alamitos： IEEE Computer Press，2012：1-11. [3] 刘强，毛玉明，冷甦鹏，等.无线传感器网络中多sink节点优化部署方法[J]计算机应用，2011（9）. [4] 徐久强，柏大治，罗玎玎，等.遗传算法在WSNs多Sink节点布局中的应用[J].东北大学学报：自然科学版，2008（6）. [5] 任秀丽，梁红伟，汪宇.基于多路径蚁群算法的无线传感器网络的路由[J].计算机科学，2009（4）.
[H（s'）=-kt∈siP（Eit）logP（Eit）] （9）
其中[H（s'）]为剩余能量熵，其值越大表示节点的剩余能量越平均，网络生存时间越长。由于式（5）中的[（4π）2β/（GtGrλ2）×P0，t]为常量，因而Sink节点[Si]的能耗评价指标可定义为：
[?cost（Si）=-d2i，jd20×H（S'i）] （10）
本文使用包含任务执行时间和网络生存时间二个分项指标的综合评价指标来衡量任务分配控制策略的优劣，使用一个比例调节系数[α（0<α<1）]来控制两个分项指标对综合评价指标的影响程度。综合评价指标[M]可定义为：
[M=α×max（?t（Si））+（1-α）×i=1n?cost（Si）] （11）
2 基于量子蚁群算法的任务分配控制策略
多Sink节点下的任务分配方案属于NP类组合优化问题，可行解的规模随Sink节点的增加将呈几何倍数据增长，由于任务分配必须具有实时性，能随时响应网络的变化，因此本文引入蚁群智能算法来解决这一问题。量子蚁群算法是对传统蚁群算法的一种改进，它采用一组量子比特概率幅值来表示蚂蚁的当前位置，用量子旋转门来实现蚂蚁的移动，用量子旋转门角度的更新实现信息素的增量。这种改进，增加了种群的多样性，避免了传统蚁群算法容易出现过早收敛的缺陷。
在[t]时刻，传感器网络中当前的任务总数为[N]，Sink节点的数量为[R]，蚁群规模为[m]，蚁群集合记为[Ω=X1，X2，…Xm]，蚁群初始化时各蚂蚁按式（12）所示的量子概率幅值选择处于某个Sink节点，其接受任务的数量按式（13）给出的概率随机选择。
[Xk=cosθk1sinθk1cosθk2sinθk2……cosθkRsinθkR] （12）
其中[θij=2π×rnd]，[rnd]为（0，1）间的随机数
[Pk（i，n）=τ（i，n）αη（i，n）βn?Jk（n）τ（i，n）αη（i，n）β0，n∈Jk（n），n?Jk（n）] （13）
其中[α]，[β]为常量，[τ（i，n）]为各Sink节点的任务选择信息素痕迹，[Pk（i，n）（1 [η（i，n）=1/M（i，n）=1/（α×（?t（i））+（1-α）×（?cost（i）））] （14） 蚂蚁K选择完当前Sink节点的任务数后，由位置[Xr]移动到位置[Xk]的规则如式（15）所示，概率随机选择下一个Sink节点的概率如式（16）所示。 [Xs=argmaxxs∈Xτ（Xs）αη（Xs）β] （15） [P（s）=ρss?gk（n）ρs，s?gk（n）0，s∈gk（n）] （16） 其中[P（s）]为Sink节点被选择的概率，[ρs]为一选择常数，[gk（n）]中记录了蚂蚁K已经选择过的Sink节点。信息素根据式（17）进行更新，增加的信息素按公式（18）计算。 [τ（i，n）new=ρτ（i，n）old+k∈ΩΔτ（i，n）k] （17） [Δτ（i，n）k=QMk，select0，not] （18） 量子旋转门和变异处理按文献[5]中的方法进行，进行多代进化计算后，各Sink节点上对应的信息素浓度最大的任务数量即为最优的任务分配方案。 3 实验数据 为了验证任务分配策略的有效性，在OMNet++4.1仿真软件基于Castalia传感器节点模型创建传感器节点，在监测区域部署120个传感器节点，分别使用2～25个并行Sink节点的不同Sink节点数量下进行了任务执行时间和通信能耗的仿真，同时在相同的节点数和任务数下与使用单一Sink节点的网络在任务耗时和通信能耗二个指标下做了对比实验，实验结果如图1和图2所示。 从实验结果可见，基于量子蚁群算法的任务分配控制策略，能较好地根据Sink节点的当前状态合理有效的分配任务，并行完成数据的处理、传送任务，相对于使用单一Sink节点的传感器网络提高了任务执行效率，降低了节点能耗，同时能获取更大的网络生存时间。 4 结束语 针对使用单一Sink节点的无线传感器网络存在任务执行效率低，能耗大能缺点，该文提出了一种多Sink并行的传感器网络结构，通过多Sink节点的并行处理来提高任务处理效率。在此基础上设计了一种基于量子蚁群算法的多Sink节点任务分配控制策略，实验证明该方法能根据Sink节点的工作状态分配任务，均衡各Sink节点的负载，减少任务执行时间和通信能耗，增加了网络生存时间。 参考文献： [1] HONG C， KUMAR S P. Sensor networks： evolution， opportunities，and challenges[J]. Proceedings of the IEEE，2013，91（8）：1247-1256. [2] Krishnamachari L， ESTRIN D， WICKER S. Impact of data aggregation in wireless sensor networks[C]// Proc of Int Workshop of Distributed Event Based Systems. Los Alamitos： IEEE Computer Press，2012：1-11. [3] 刘强，毛玉明，冷甦鹏，等.无线传感器网络中多sink节点优化部署方法[J]计算机应用，2011（9）. [4] 徐久强，柏大治，罗玎玎，等.遗传算法在WSNs多Sink节点布局中的应用[J].东北大学学报：自然科学版，2008（6）. [5] 任秀丽，梁红伟，汪宇.基于多路径蚁群算法的无线传感器网络的路由[J].计算机科学，2009（4）.
