低能耗和低时延的无线传感器网络数据融合算法

摘要：针对无线传感器网络的节点能量有限，且在进行信息传输时存在数据冲突、传输延时等问题，提出并设计了基于最大生存周期的无线传感器网络数据融合算法。该算法将整个网络中的节点分成多个簇，并根据节点的传输范围，将每个簇中的节点均匀分布，每个节点根据自己的本地信息和剩余能量选择通信方式向簇头节点传输数据，从而形成传输数据的最短路径；并根据集中式TDMA(时分多址)调度模型，运用基于微粒群的Pareto优化方法，使得网络在完成规定的信息传输时每个节点耗费的平均时隙和平均能耗最优。仿真结果表明，上述算法不但可以最大化网络的生存时间，还可以有效的降低数据融合时间，减少网络延时。
关键词：无线传感器网络；数据融合；能耗；延时；时分多址；微粒群；生存时间；Pareto优化

    无线传感器网络(Wireless Sensor Network，WSN)是由分布在检测区域内大量的静止或移动的传感器组成，它们是通过自组织和多跳的方式形成的无线网络，可以协作地感知、采集和处理检测区内的各种信息，并把信息传送给用户终端，是一种新兴的信息获取和处理技术。WSN可应用于恶劣环境和无人环境下信息的采集和传送，同时，它还具有布设灵活、成本低、范围大等特点，日益受到人们的关注，是当前国际备受关注的研究热点之一。
    在无线传感器网络中，若各个节点在采集信息时，采用单独传送信息到汇聚节点的方法，则会造成网络过多能量的消耗和传输信息的频繁冲突碰撞。因此，使用数据融合的方法来减少网络中信息传输的总量，从而达到节能和提高信息传输效率的目的。它不但可以采用一定的算法将传感器节点采集到的大量原始数据进行网内处理，去除其中的冗余信息，而且还可以在融合前减少汇聚节点等待非汇聚节点信息
传输的时间，减少网络中数据融合的延时时间。

1 无线传感器网络的数据融合算法
1．1 数据融合概念的描述
    在无线传感器网络中，数据融合是在一定的准则下对按时间顺序获得的若干传感器节点的检测信息进行自动分析、融合，以完成所需要的估计任务和决策进行的信息处理过程。
1．2 节点剩余能量的计算
    假定节点的初始能量为Er，并且在T1时刻之前，网络分别进行了n1次、n2次的信息发送和接收，则节点i存T1时刻的剩余能量可用公式(1)表示
   

2 低功耗无线传感器网络数据融合算法
2．1 节点数据结构
    传感器节点i需要维护的信息包括：1)簇头节点Pi；2)节点的剩余能量标志位Hi：设置能量阈值ST，若节点i剩余能量值为Si，当Si<ST时，则置Hi=0，并通知邻节点不再向i发送信息；否则置Hi=1，可以进行下一次信息的接收或者发送。
2．2 算法描述
    假设在检测区域内存在多个传感器节点，我们将其分为多个簇。而后根据各个传感器节点的传输距离，对每个簇内的节点进行均匀布置，如图1所示。

    首先，根据网络中每个节点的自身信息来决定各个簇头节点，而后由它们来启动数据融合算法。由于网络中各个簇头节点的选取都取决于自身的信息，因而会导致网络的结构和每个节点的位置处于不断变化之中，若选取几个固定的节点势必会造成较大时间延时和能量消耗。基于上述原因，为了保证每次选取的初始节点不同，应该选择距离基站最远的节点作为初始节点，由它们启动融合算法，从而最短化簇头节点到基站的距离，降低数据融合的延时和能耗，最大化网络的生存周期。
    每个簇中数据传输的过程为：首先，簇头节点检测自身的剩余能量Si，若Si>ST，置Hi=1，并向所有可到达的传感器节点发布自己的位置信，否则簇头节点广播信息使得其他节点进入休眠状态。我们假设簇头节点的剩余能量Si>ST，则簇头节点向非簇头节点广播自己的位置信息，非簇头节点i在接收到这一信息后，判断自己到簇头节点的最小跳数和距离其最近的节点i的剩余能量，若其剩余能量Si大于能量阀值ST，且到簇头节点的跳数小于节点i到簇头的跳数，则节点i选择节点j作为父节点，并向父节点j发送加入请求，否则置Hj=0、Fj=0，告诉邻近的节点不要再向j发送信息，并使自己进入长期休眠状态，而后节点i重复上述过程，直到选出父节点为止。
    如图1，簇头节点9首先启动运算并检测自身的剩余能量值S9，若S9<ST，则置H9=0，并向其它节点广播信息，使其它节点进入休眠状态；若S9>ST，则置H9=1，而后簇头节点9把自己所在的位置告诉邻近的非簇头节点，由它们自己判断到簇头节点9的最小跳数和剩余能量，并把信息反馈给簇头节点9，由其选择那些非簇头节点可以加入其为簇头节点的簇内。图1中，节点1判断自己到簇头节点9的跳数为4跳，且距离其最近的非簇头节点4的剩余能量为S4，虽然节点4距簇头节点最小跳数为3跳小于节点1到簇头节点的跳数，但是由于S4小于ST，节点4仍不能作为节点1的父节点，而后继续判断距离簇头节点9较远但到簇头节点9的跳数仍为3跳的节点5的剩余能量，由于S5大于ST，所以节点1选择节点5作为父节点，同理，5的父节点为7，7的父节点点为8，8的父节点为簇头节点9，至此一个簇建立完毕。
2．3 时隙分配方案
    节点在信息传输的过程中，可能存在空闲侦听、传输碰撞等现象，从而导致传感器网络在进行信道访问时存在较大的时延和能量消耗，因此设计了一种新的TDMA调度方案，并运用基于微粒群的Pareto(简称PAPSO)优化方法，使得无线传感器网络在完成规定的信息传输任务时每个节点的平均时隙和平均能耗最优。
2．3．1 优化目标
    把初始节点传送的信息在经过单跳或多跳通信方式到簇头节点的过程，称为一个事件，信息每次跳转传输的过程称为一个子事件，一个子事件对应一个执行节点，并占用一个时隙，则无线传感器网络完成指定任务每个节点的平均时隙和平均能耗分别以f1和f2表达，如下所示。

    完成此次传输事件时的总接收时间。通过公式(2)和(3)可知，通过减少网络中各个环节的切换能量和时隙的个数，就可以最大化网络的生存周期。
2．3．2 个体的编码与解码规则
    要优化TDMA分配，首先应找到事件与问题间的对应关系，而后在解的空间内搜索最优解，由2．3．1节可知，把信息传输的过程看作是由一系列子事件组成的，因此一个事件可被记为(事件编号，顺序号)，其中，事件编号是指该子事件属于那个事件，顺序号则指信息传输过程中每一个子事件执行的顺序编号。
    综上，可以将每个无冲突的事件按一个顺序进行编码，继而按顺序给它们分配时隙。这就是由编码规则得到的个体与TDMA调度方案之间的映射关系的解码规则。
2．3．3 基本粒子群算法
    粒子群算法最早是由Kenney和Eberhart在1995年提出的，是一种新的模仿鸟类群体行动的自能优化方法，缩写为“PSO”，它与遗传算法一样，是从随机解出发的，可通过适度评价解的好坏，并通过迭代的方法寻找最优解。PSO迭代方程如下：
   
    其中：“i”表示微粒：“d”表示微粒的第d维；“t”表示第t代；Vid表示微粒i的速度；Xid表示微粒i的位置；Pid表示微粒i的个体极值(p_best)，Pgl表示所有微粒i全局极值(g_best)；W表示惯性权重；C1、C2表示学习因子；r1、r2表示介于(0，1)之间的随机数。
2．3．4 多目标微粒群算法解的评价机制
    在多目标优化问题中，可以用多目标的加权和方法和Pareto优化方法作为评价机制为微粒群的搜索方向提供依据。
    PSO是粒子通过跟踪两个“极值”来为自己提供搜索方向的，一个是粒子本身的p_best，另一个则是g_best，因此使用粒子的p_best和g_best相结合的方式对多目标解进行评价。
    1)粒子自身p_best的评价

    2)全局最优解的评价
    TDMA调度中是以任务完成时每个节点的平均时隙数和平均能耗最优作为指的标，但由于在一定的任务条件下，要求每个节点的平均能耗和平均时隙最优，即是要求节点工作的连续性很好，即是要求父节点应接收完所有子节点传送的信息后，才进行下一次信息跳转的传输，这样必会增加节点的平均时隙数，反之亦然。由于任务完成时每个节点的平均时隙数和平均能耗不能同时达到最优，加权和方法很难完全评价解的好坏，因此，引入Pareto优化方法，来评价解的好坏。对于一个最小化M个目标的问题，使用支配概念，其定义如下：minF=[f1，f2，…，fM]，若要X1支配X2，则在解空间内必存在任意两个解X1、X2满足如下条件：
    ①在解空间内，一定存在一个X2比X1大，即fj(X1)≯fj(X2)，j∈(1，2，…，M)；
    ②X2一定有一个在目标上是严格比X1大的，即fj(X1)<fj(X2)。
    如果解不满足①和②中的任意一条，则称X1不支配X2，即X1是X2的非支配解，所有的非支配解构成非支配解集，若非支配解的求取是在整个解空间内进行时，则称该非支配解为Pareto最优解。
2．3．5 PAPSO优化方法实施步骤
    PAPSO实施步骤：
    1)对粒子进行初始化，即设定粒子的个数为np，迭代次数Nmax，产生np个随机初始值X；并初始化W、C1、C2、和p_best的值，并把当前的粒子位置设置为p_best；用评价机制对粒子的p_best进行评价，找到g_best，而后计算出目标函数F中的每个目标值，用Pareto优化概念，找出作用于整个解空间的非支配解，从而初步形成一个Pareto解集。
    2)进行迭代运算，用式(4)和式(5)产生下一代微粒群。
    3)应用评价机制对X(j)和p_best(j)进行评价；如果f(X(j))>f(p_best(j))，则p_best(j)=X(j)；更新所有个体的最优位置和全局的最优位；应用支配的概念，找出非支配解集，进而找出Pareto解集。
    4)满足迭代条件(有此以迭代代数作为条件)，输出最后一代的种群个体(即Pareto最优解集)；否则，执行步骤3)。

3 仿真及其分析
    在一个二维环境中进行试验，169个节点被均匀的放置在600 m2的网格区域中。
    仿真试验中，每个节点的信道容量为500kbs，并在可以形成链接的通信范围内，设定通信距离为15m。节点活动状态和睡眠状态的切换时间是470μs。以一个数据包的传输时间和可能的时钟偏移时间之和作为TDMA时隙的大小。发送和接收一个数据包所需的功率是81mW和180mW。
    基于上述的网络模型，分别对LEACH、DEEC及新算法进行了仿真，重点比较和分析了3种路由算法运行过程中网络的生命周期。
    图2为运行过程中整个网络生命周期对比的仿真。由图可见，如果一个网络中节点的初始数目相同，新算法可以使得网络的生命周期最长，LEACH算法在大约40％的节点死亡之前，其性能比DEEC算法差，而后它的性能要优于DEEC算法。由于新算法选择簇头时考虑了节点的剩余能量，当节点剩余能量较小的时候，将选择距离其最近的节点作为簇头，继续进行信息的传输，且由于选择了最短传速路径和最优了时隙分配方案，所以在完成传输任务是每个节点消耗的平均能量和平均时隙最优，最大化了网络的生存周期。

    仿真实验还比较了NBSA算法和PAPSO优化方法用于TDMA调度方案时，网络中每个节点在完成规定任务时的平均能耗和平均时隙。在多目标粒子群Pareto优化方法中，取C1、C2和W分别2．0和1．5，微粒群的个数为40，迭代次数为600。
    从表1不难看出PAPS01虽然平均能耗是7个中最差的，但平均时隙却是7个中最少的，而PAPS07则与PAPS01相反，平均能耗虽是7个中最少的，但平均时隙却是最多的。它们之间分还布着其余5个解。

    由于这7个解的是均匀分布的，因此，目标f1、f2的中间解为PAPS04。依Pareto优化概念对各算法的结果进行分析，由图3显见，PAPSO(1—4)对NBSA构成支配。可见多目标粒子群Pareto优化方法能得到比NBSA更好的调度结果。

4 结论
    在无线传感器网络中，为减少信息传输过程中的时延和能耗，提出了基于最大生存周期的数据融合算法，并结合对TDMA调度，提出了相对应的PSO—Pareto优化方法，从而在信息传输的路径和每个节点完成规定任务所需的平均时隙、平均能耗两个方面论述了减少网络的时延和能耗，最大化了网络的生存周期和最小化了网络的延时。