最佳任务分配下的传感器网生存期定限问题.docVIP

最佳任务分配下的传感器网生存期定限问题 摘要 在用于数据收集的ad-hoc无线传感器网中，一个关键的挑战是如何使一个仅仅储存着几百焦耳能量的节点能够工作几年。本文通过推导生存期的上限给出了面向能量有效的数据收集传感器网的基本极限准则。 总结 本文的主要工作是讨论无线传感器网生存期的最大极限。提出了一种对任意复杂的网络都可以推导出生存期上限的方法（尽管计算的复杂度会很高）。事实上，在几种特定的情况下，包括允许数据融合的特定拓扑结构的传感器网，该方法计算复杂度转化为多项式形式时间。 本文引入形式化的合理任务分配（FRAs）来推导生存期极限。认为所有不存在冗余节点的FRAs构成一个有限的集合。基站收到的每一个比特都是通过该集合中某些FRAs来完成的。这样问题就转化为：使用哪些FRAs可以使生存时间实现最大化。 任务分配的方法直观而且好用，它可以通过线性规划求解任意复杂的数据收集网络还可以yield crisp bounds。有一类任务分配问题可以转化为在多项式时间内求解的基于网络流的线性规划，这一类问题包括：纯路由、无分级或强制分级融合、多目标或移动目标、特定轨迹的目标……等情况。 研究的问题 1、研究了传感器网络节点任务分配的有关问题。 2、利用任务分配模型给出固定单目标的网络生存上限。 3、将模型推广至任意区域多目标移动的情况。 准备工作 基本操作 目标区域或观测区域称之为R，基站称为B（图一）。在任何给定情况下，传感器网络中的节点都可以根据有无能量剩余而被分为live或dead。通过分配不同的任务，live节点之间通过协作确定何时目标在R内，并将合成的结果通过最小数量（k）的传感器传递到基站B。在协作模型下我们假定一个任务是由一个或多个下列子任务组成： 感应：节点通过传感器观察目标，将信息数字化，进行预处理并将其发送出去。该任务具有一个属性，接受该原始信息的目的节点。 传递：不进行任何处理的转发。该任务具有两个属性，源节点和目的节点。 融合：节点接收到两个或两个以上的原始数据流并将其融合成一个。因为不通的感应器可能同时感应到同一个目标，但是可信度又有差别，因此需要将这些信息进行融合。我们将融合分为不分级和分级两类。前者是将所有原始数据流融合成一个数据流。后者是选取部分原始数据流将其融合成一个数据流。融合子任务有两个属性，传送原始数据的节点集合和接受融合数据的节点。 图一 定义生存期 一个数据收集网络可能会处在下列情形之一： 目标出现在目标区域内但是没有被发现，称之为“覆盖丢失” （“loss of coverage”）。 目标出现在目标区域内，被感应到且满足使用者的要求，称之为“活跃” （“active”）。 目标出现在目标区域内，被感应到但不满足使用者的要求，称之为“质量失格” （“quality failure”）。 没有目标出现在目标区域内。 在任务要求不严的情况下，生存期可以被定义为网络的累计活跃时间；而在任务要求严的情况下，生存期被定义为网络的累计活跃时间到第一次出现“覆盖丢失”或“质量失格”为止。 节点组成和能量模型 集成无线传感器节点具有图二所示的结构： 感应核心: 假定在该核心要将个原始数据流融合为一个。感应一比特信息需要的能量为定值，感应速率为bit/sec，感应功率就可以表示为：。的典型值为50 nJ/bit。 计算核心：假定在该核心要将个原始数据流融合为一个。 表示数据流的速率，单位是bit/sec，是常数。注意只表示计算核心的能量消耗，接受和传送数据的能量消耗是分别计算的。参数根据融合的类型以及使用的结构不同，其取值范围从pJ/bit到nJ/bit不等。 通信核心：使用下列模型计算通信核心 其中是从节点传送到消耗的功率，表示节点 到的距离，是路径损耗指数，是正常数。这些参数经典取值为=45 nJ/bit,=135 nJ/bit, =10 pJ/bit/m2 (n=2) 或 0.001 pJ/bit/m4 (n=4) 。 模型建立及问题的解决 在参考文献〔11〕中，我们解决了下面的问题： 给定观测区域R，节点可观测半径，节点能量参数和n，节点总数N，节点初始能量E，目标于R内存在服从特定的空间概率分布，其概率密度为。以上条件已知，如何求出生存期的上限。 推导紧或近似紧边界的关键步骤如下： 1）计算将1比特数据传送一定距离的最小累积能量。要考虑所有可能多跳拓扑结构，如果是距离的凸函数，则这个最小化问题就变得很容易计算。 2）推导在ad-hoc网路中期望功率损耗的下界。 3）根据能量守恒由平均功率损耗的下界推出生存期的上界。 使用以上方法，对于目标存在于观测区域某处的数据收集网络的生存期上限可以求得： 是关于R