（计算机软件与理论专业论文）无线传感器网络中基于信号相关的目标计数.pdf

摘要 摘要 无线传感器网络在近几年受到了学术界和工业界的广泛关注。由于无线传感 器网络能够嵌入物理环境，近距离地观察环境，并通过传感器节点间的数据融合 获得关于所监视环境的各种有用信息，无线传感器网络在工业、农业、交通、军 事、安全、环保等众多领域有着广泛的应用。 目标监视是无线传感器网络的重要应用之一，其内容包括目标检测、定位、 计数和跟踪等。已有的研究工作大多集中于对单个目标的监视和跟踪，一般的做 法是将检测到目标信号的节点组成一个簇，用这组节点的质心或这组节点感知区 域的重叠部分的质心作为目标的估算位置，进而得到目标的运动轨迹，并预测目 标的下一步运动。当传感器节点只配备简单的能量传感器( 只能检测目标信号的 能量) 时，区分监视区域中的多个目标是一件非常困难的事，因为传感器节点检 测到的信号是由多个目标信号叠加的结果。目前多目标计数的研究工作大多采用 基于能量的方法估计目标的个数，即假设同类目标发出的信号能量是相同的并且 是已知的，通过计算分布在局部感知区域内信号的总能量来估计该局域内的目标 个数，不同算法的区别在于如何估计信号的总能量。 本文根据来自同一目标的信号序列具有较大相关性的观察事实，提出了利用 信号相关性解决多目标计数问题的设想。对各节点采集到的目标信号序列计算相 关性，将信号相关度大于一定门限值的节点划为一组并对应一个目标，从而实现 目标计数和每一组内的目标定位。仿真实验表明，该算法在计数精度和目标定位 精度方面与基于能量的目标计数算法相当，但由于该算法不需要假设目标信号能 量相同，从而比这些算法具有更好的适应性。另外，本算法通过良好的算法设计， 也控制了算法的计算和通信复杂度。 关键词：无线传感器网络，目标计数，信号相关性 d g o “t h mi sm o r ea p p l i c a b l es i n c ei tr e l a x e st h er e q u i r e m e n tt h a te a c ht a r g e ts h o u l d 量l a v e 也es a m es 适n 越s t r e n 寥h 。m e a l l 劬i l e ，也i sa l g 蠢t h 趱e o n l 瓣l s 橇ee o m p l e x i 毫yo f c o m p u 雠i o na n dc o h 疆n u n i c a t 主o nb ye x c e l l e n td e s i g n i n g 1 ( e y w o r d s ：w i r e l e s ss e n s o rn e t 、o r k ，t a 略e te o u n t i n g ，c o n e l a t i o 娃o fs i g n a l s l v 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：函壑煎 2 卅年莎月。厂日 第l 章绪论 第 章绪论 伴随着无线通信和电子技术近年来的飞速进步，无线传感器网络作为一种由 低成本、低功耗、多功能的传感器搀藏豹瓣络，正受至l 越来越多躲关注。 无线传感器隧络的设计、实现以及应瘸涉及到多f l 学科的知识，雹括信号处 理、网络路由、嵌入式系统、信息管理和分布式算法。它用于监测物理环境，收 集翱缝理数据，将感知到的信息传送给感兴趣的用户，具有广蠲的应用前景和深 远盼研究价僮，其应嗣覆盖了人类生活静缀多方露，铡如环境监测、王厂制造、 商务管理、交通以及卫生保健等领域。 本章首先介绍无线传感器阏络的基本知识，目标计数问题所从属的目标监视 闻题。之焉贫绍蹙标计数阕题麴背景和研究现状，最后绘壤本文磺究蠹窭。 1 。1 无线传感器网络简介 无线传感器网络是由部署在监测区域内的大量微型传感器节点通过凭线通 信方式形成的一个多跳、自组织的厨络系统，其目的是协作地感知、采集和处理 嬲络覆盖区域串被感知对象的信息，著发送给溉察者。传感器、感知对象释观察 者构成了无线传感器网络的三个要素。 传感器节点一般由传感单元、处理单元、收发单元、电源单元等功能模块组 成，其结构如图1 1 所示。除此之外根据具体应用的需要，可篷还会有定缀系统、 毫源襻生单元帮移动单元等等。 嚣1 1 传感器繁点麴结稳 传感器网络一般其有如下特点： 差) 节点体积小、成本低、计算和存储能力有限。 第l 章绪论 由于无线传感器网络一般用于菲侵入式的环境监视，因此节点通常做得比较 小。此钋，在一些不适宣人类活动的地方( 如野钋及有害环境) 部署的传感器网 络，节点回收困难，节点大多是一次性使用，因此每个节点的成本都比较低。由 于体积和成本的限制，其处理器和存储器的能力都很有限。 2 ) 传感器网络具有鲁组织能力和适应性。 根据应用的不同，传感器节点的数量可能达到数万个甚至更多，因此很难手 工实现网络的初始化以及之后的网络维护。这就需要传感器节点能够在被激活后 通过彼此间的通信与协调实现网络的初始化与之后的维护工作，即需要传感器网 络具有鲁组织能力。同时，传感器嬲络往往工作在比较恶劣的环境中，节点或节 点间的通信出现故障是很常见的，这就需要传感器网络具有好的健壮性和容错能 力，也就是适应性。 3 )电源电量是网络寿命的关键。 无线传感器网络通常工作在人类无法接近的恶劣甚至危险的远程环境审，无 法提供电力供应，因此传感器节点只能选择电池供电。由于电池电量有限，因此 节能成为传感器网络设计的第一要素。 4 ) 节点通信距离短，通信带宽低。 传感器节点的通信距离一般只有几十米，因此必须采焉多跳的方式进行数据 传输。另外，传感器节点的通信带宽很低，丽通信消耗的能量最多，因此在传感 器网络中传输的数据最好是经过预处理、消除了冗余的数据。 5 ) 数据管理与处理是传感器网络的核心。 对观察者来说，传感器网络的核心是数据。这就要求传感器网络的设计必须 以数据为中心，把数据库和网络技术紧密结合，从逻辑概念和软、硬件技术两个 方面实现一个高性能的以数据为中心的网络系统，使用户如同使用通常的数据库 管理系统和数据处理系统一样自如地在传感器网络上进行感知数据的管理和处 理。 总之，一个无线传感器网络可以抽象表示为g = 。这里v 表示传 感器节点集合，e 表示节点间的通信状态，p v 为一系列表示v 中节点特征的函数， 例如节点位置、计算能力、感知模型、传感器输瀣值类型和节点能量储备等，p e 描述节点闻通信状态的性质，如通信带宽和质量等。 1 。2 目标监视问题简介 酲标计数是露标监视闯题的一部分。在介绍西标计数溜题之前，本节先对雷 标监视问题做一个简要介绍。在目标监视应用中，当目标出现在监测区域时，传 第l 章绪论 感器节点应能及时发现目标，确定目标的类型，估计目标的位置，进而得到目标 的运动轨迹。 当目标出现在监测区域时，目标附近的传感器节点应能检测到目标发出的诸 如声音、振动等信号，有时外界的干扰也可能使传感器节点检测到假阳性信号。 单个传感器节点由于功能有限无法判断信号是来自某个目标还是外界干扰，因此 传感器网络首先必须通过节点间的协作判断目标是否出现。在有些应用中，当判 断目标出现后还需要进一步识别目标的类型( 目标识别) ，以及估计目标的位置 ( 目标定位) 。如果监测区域中只有单个目标，则确定目标在不同时刻的位置后 即可得到目标的运动轨迹。但如果有多个目标出现，则首先需要确定目标的个数 ( 目标计数) ，然后结合目标定位技术计算每个目标的运动轨迹( 目标跟踪) 。 总之，目标监视问题可以看成是一个约束优化问题 。其中，g 为传感器网络的抽象表示；t 为目标集合，包括目标的位置、形状和目标信号的 类型：w 是信号模型，包括目标信号的传播和衰减模型；q 表示用户的请求，例 如。估计区域内目标个数 和“跟踪目标 ；j 为由任务而决定的目标函数，例 如在目标定位任务中，目标函数为定位的精度；最后，c = c l ，c 2 ，” 为一系列 约束条件，例能耗的约束等。 目标监视是无线传感器网络的一项重要应用。它体现了在协作处理、信息交 互和节点组织管理等信息处理和组织方面的重要问题。这些问题包括在在一个动 态变化的环境中激活哪些节点，哪些节点的信息有价值因而需要被传送，哪些节 点需要接收信息，以及接收的频度等。下面分别介绍目标识别、目标定位和目标 跟踪。 1 2 1 目标识别 当目标被发现后节点会根据感知到的数据对目标类型做出推断，系统会根据 各节点的推断做假设检验，最后确定目标类型。这是一个确定所感知信号的相关 参数的过程，这些参数可以是信号的峰值能量、相位、持续时间和能量谱密度等。 相应的目标函数为将第i 类目标归入第i 类的概率昂，以及将第i 类目标归入 第j 类的概率尼( 幻) 。 目标往往会产生多种信号，例如一辆运动中的汽车可产生声音、热、磁、振 动等信号。根据目标信号的类型可以选择不同的传感器，而由于不同信号的特征 不同，其适用环境也会有所不同。因此需要根据不同的任务选择合适的传感器。 一般来说，温度传感器具有高灵敏度，但易受障碍物影响；声音、振动传感 器则不受障碍物影响，不过相应的信号处理算法具有一定的时间和空间复杂度； 磁力传感器则限于含铁的目标。 可以利用多种传感器来识别目标。 2 中使用磁力传感器来识别车辆和士兵。 第l 章绪论 因为车辆的磁力影响范围比士兵大，感知到车辆的节点构成的凸壳的面积比感知 到士兵的节点构成的凸壳面积大很多，所以感知到信号的磁力传感器节点会向基 站节点报告，由该节点计算出簇中节点构成的凸壳面积，并以此判断冒标的类型。 同时， 2 在网络中放置了少量的雷达来识别普通人和士兵。当目标是普通人时 只有雷达发现了目标，而当士兵出现时雷达和磁力传感器均发现目标。基站节点 可以投据雷达和磁力传感器的报告来区分普逶人和士兵。 由于不同类型物体的声音和运动时的振动等信号具有不同的特征，因此可以 提取声音等信号的特征矩阵，根据它来识别不同的物体。 4 中感知到声音或振 动信号的节点将提取的信号特征向量发送给基站节点，基站节点收到各节点发来 的特征向量后计算特征向量的平均值，以此来判断目标类型。它的准确度依赖于 参与协作的节点数，参与的节点越多则越准确，当然通信消耗也越大。 9 中感 知到信号的节点在提取特妊向量后，先在本地对目标类型做出判断，再向基站传 送本地的判断结果和该结果为真的概率。基站则根据所有节点发来的信患做出最 终判断。该方法极大减轻了网络的负载，不过运行本地识别器的节点需要耗用较 多的计算资源。 露蓠对善标识别阍题的磷究都是骰定监测区域中只有一个墨标，即使区域内 有多个目标，各目标的影响范围也互不重叠。这是因为传感器节点受到自身能力 的限制，难以分辨出感知范围内出现的目标的个数。 1 。2 。2叠标定位 目标定位是指估计出某一时刻的无线传感器网络内被监测目标的空间位置。 根据信号测量物理量的不同，目前的目标定位技术主要分为三大类：基于时差定 位( 零d 激) 、基于信号方向定缀( d 隘) 和基于接收到的信号能量定位( r 鲻王) 。 t d o a 方法测出信号到达两个节点之间的时间差，由此求出距离差，从而计 算出网标的位置，如 1 2 ，1 4 。d o a 方法利用信号来源方向的不同来定位，如 1 0 。 t d 馓方法用于宽带信号，对时间差的测量精度要求很高，丽d 激则用予窄带信 号。这两种方法都对信号的频带很敏感，它们的计算比较复杂，相应的能耗较高。 而且t d o a 对传感器节点的放置也有一定的要求，一般而言传感器节点需要成对 出现，且对延迟时闻的估计需要很高的精度，否则误差会很大。 r s s 王利用声音能量在空气中传播时隧距离成一定比例衰减的特性，逶过多 种数据处理方法来估计目标位置。 1 5 采用极大似然估计法估计目标位置。它根 据传感器节点感知的信号能量构造一个极大似然函数，在监测区域中使该函数值 最大懿点帮为冒标的位置。 s 】以感知到誉标的所有节点的加权质心为基标的位 置，其权值即为各的节点权值越大，这样的节 点越多则得到的加权质心与实际目标位置越接近。 4 第l 牵绪论 利用目标、环境和节点的信息来对假设做排列，减少假设的数量。 卡尔曼滤波器或委叶囊滤波器馁设在穿列曼薪时数据有严格翡辩阆缀序，嚣 传感器网络中节点闻的传输延迟会导致这些滤波器不得不回退整个跟踪算法以 添加一个过去某一时刻的测爨值，或只是简单的丢弃过时的数据。 8 的分布式 专尔曼滤波器是个全是的数据关联方法，要求每个节点将感知的数擐传送到基 站，疼基菇负责估计和跟踪。这样，感翔是分布式豹，丽鼹踪是集中式鲍。这会 导致较高的通信代价，且网络的通信链路并不总是有效的 1 3 謦标计数阊题简奔 1 。3 1目标计数问题背景 嚣标监视是巍部署在野外环境燕战场、生态保护区) 孛抟黄感器节点通过 感知目标发出的信号( 如声音、振动、辐射等) 检测目标的出现，并通过协同计 算对目标进行定位与跟踪。根据监测环境中目标的个数，目标监视可分为单目标 监视和多霾标监视。 目前大部分的茸标监视问题为单目标蘸视，因此无需考虑目标计数。它兵需 根据感知到的声音、振动等目标信息来发现、识别目标，进而实现定位与跟踪。 瑟多星标篮视阅题翔复杂很多，它首先需要解决熬是确定监测区域中的叠标个 数， 蔓就是蓦标计数砑题。 在真实的监视场景中，目标在监测区域内可以以任意方式运动，因此两个或 两个以上晷标的运动轨迹很有可能发生交汇。同时，由于受到传感器网络自身的 限制，传感器节点酶惑黧麓力有限，当多个嗣标提距最近时，并不容易分辨基标 个数，因此目标计数问题并不容易解决。 3 2尽标计数问题的研究现状 【7 】使用二元传感器来信计誉标个数。二元传感器是仅报告霉标是否遗现酶 传感器，它是对各种传感器的简化。二元传感器不具备任何特殊的功能，例如输 出所感知声音信号豹能量，因此输出的数据值很简单，网络处理和传输数据时耗 能很少。【? 3 利用二元传感器估计一维基域中霜标戆令数，经过推理得感冒标计 数问题的精度：若传感器节点的感知半径为r ，则长度为2 m r 的区域最多能准确 辨识m 个目标。 l s 】剥震节点感翔翡蔷号能量估计蠢标个数。壹予声音等信号在传播时能量 随距离增加而量指数倍衰减，因此文中利用备节点感知的信号能量对节点进行分 簇。所有检测到信号的能量超过某个阈值的节点均参与簇头的选举，最终在某个 6 第l 章绪论 局部区域内检测到的信号能量最大的节点成为簇头( 即峰值节点) ，其它参与选 举的节点归入到最近的簇头所在的节点集合中，于是目标的个数就等于簇头的个 数。当目标相距较近造成信号影响范围重叠时，一个簇可能会对应多个目标，此 时上述方法会造成计数不足。 为解决这一问题， 1 6 进一步提出了一个基于信号能量的目标计数算法 e b a m 。该算法假定目标发出的信号能量均相同且已知，通过计算簇中各节点感知 的信号能量的加权和来估算簇内目标信号的总能量，然后除以单个目标的能量即 得到簇内目标的个数。【1 3 】的e b t n 算法采用一个多项式函数来拟合簇内节点的 信号能量值，通过积分计算簇内信号的总能量，并以此估计每个簇对应的目标个 数。以上方法都要求目标的信号能量相同且已知，而且需要较大的节点密度来提 高分簇及能量估计的准确度。 1 4 论文内容 本文利用传感器节点检测到的信号序列的相关性解决目标计数问题。本文首 先通过模拟实验研究了利用信号相关性估计目标个数的可行性，然后提出了一个 基于信号相关性的目标计数算法s c b n ，以及基于该算法的目标定位方法。最后， 在分析了本文算法的计算与通信复杂度后，在仿真实验平台上比较了s c b n 算法 和基于信号能量的目标计数算法e b a m 与e b t n 的计数精度。仿真实验表明，在相 同的节点密度和目标密度下，s c b n 的目标计数精度与e b a m 和e b t n 相当， 而抗噪声能力要强于后两个算法。另外，由于s c b n 不要求目标信号能量相同， 因此比利用信号能量的目标计数算法有更强的适用性。 1 5 论文组织 论文剩余内容如下安排：第2 章描述无线传感器网络中的目标计数问题，分 析介绍目标计数领域的典型算法；第3 章分析利用信号的相关性估计目标个数的 可行性，介绍本文算法的设计思想：第4 章分析算法复杂度，在仿真平台上实现 本算法，并与e b a m 和e b t n 算法作精度对比；第5 章总结全文，指出未来的工作。 7 第2 章目标计数问题 2 2 目标计数问题的研究现状 2 2 1d a m 和e b a m 算法 在目前为数不多的多目标计数研究中， 1 6 】是一个典型代表，它提出了一个 分簇算法d a m 和一个基于能量的目标计数算法e b a m 。 d a m 算法根据节点感知的信号能量来构造簇，使每个簇中仅有一个信号能 量峰值，这个峰值就代表了一个目标。d a m 通过比较邻近节点检测的信号能量 构造簇。检测到的信号能量大于给定阀值的节点均参与簇头选举，将自己检测的 信号能量和自己认可的簇头信息发送给邻居节点，每个节点初始时选择自己为簇 头。每个节点保存两个信息：( 1 ) 自己认可的簇头及簇头检测的信号能量；( 2 ) 父 节点及父节点检测的信号能量。当节点a 收到邻居b 发来的簇头选举消息时， 检查消息中携带的信号能量信息。如果b 检测到的信号能量大于a 检测到的信 号能量，且b 认可的簇头b h 检测到的信号能量大于a 认可的簇头a h 检测到的 信号能量，a 转发该消息，并将自己认可的簇头和父节点分别更新为b h 和b ， 否则抛弃该消息。显然在算法运行过程中，簇头选举消息从检测到较强信号的节 点流向检测到较弱信号的节点，即父节点感知的信号能量大于子节点感知的信号 能量。最终只有检测到最强信号的节点产生的消息被发送至簇内每个节点，这个 节点即成为簇头。 d a m 算法仅根据节点感知的信号能量将节点成簇，受到了信号衰减模型、 目标间距和节点密度的影响。若信号衰减速度比较缓慢，目标间距较近或节点稀 疏时一个簇会包含几个目标。仅利用d a m 算法会低估目标的个数，因此需要利 用其它信息进一步估计每个簇对应的目标个数。 【1 6 】的e b a m 算法根据簇内节点感知的信号能量的加权和估计每个簇对应 的目标个数。它要求每个目标的信号能量相同，且已知单个目标在监测区域中产 生的信号能量加权和。每个簇内信号能量加权和除以单个目标产生的信号能量加 权和，所得的商即为每个簇对应的目标个数。 在给定的网络中，当目标位置变化时，监测区域内传感器节点与目标的间距 也会发生变化。由图2 3 可见，节点与目标间距的微小变化都会给节点感知的信 号能量造成大的影响，因此当目标位于不同位置时其影响区域内节点感知的信号 能量之和会有较大的波动。为了减小这一影响，e b a m 给每个节点设定一个阀 值，若节点感知的信号能量值大于该阀值，则在计算能量之和时只认为该节点的 能量为所设定的阀值。如图2 3 所示，设c 处的信号能量值即为阀值，则与目标 间距在c c 2 以内的节点向能量之和贡献的值均仅为所设定的阀值。这一阀值不 能设得太高，否则无法抵消目标因位置的变动而对能量和的影响。由信号的衰减 i o 第2 章目标计数问题 公式( 2 1 ) 和图2 3 可知，信号在传播一定距离后其衰减速度明显放缓，因此若阀 值设得太低，则所得的信号能量值只是与阀值成正比关系，而比例因子是感知到 信号的节点数。 在节点分布不均匀的网络中，目标位于节点稀疏区域中时，由于节点与目标 的平均间距较大，参与的节点数较少，所得的信号能量之和小于节点密集区域产 生的信号能量之和，因此需要平衡节点分布不均造成的影响。 e b a m 为此对节点做v r o r o n o i 划分。v o r o n o i 划分是由连接两邻接点的直线 的垂直平分线实现的，对于平面上的每个点，按照最邻近原则划分平面，使得每 个点所在的v o r o n o i 单元即为它的最邻近区域。在节点分布不均的网络中，稀疏 区域中节点的v 0 r o n o i 单元的面积较大，而密集区域中节点的相应值较小。因此 以节点的v 0 r o n o i 单元的面积作为每个节点的信号能量值的权值，可以平衡节点 分布不均造成的影响。 当目标信号能量相同时，该方法在传感器节点均匀分布或节点密度较大时具 有良好的性能表现。不过在无线传感器网络中实现分布式v o r o n o i 划分，并对它 做维护需要消耗较大的计算与通信代价。 2 2 2e b t n 算法 【1 3 】中提出的e b t n 算法采用与 1 6 】近似的成簇算法，使得每个簇对应单个 或多个相距较近的目标，但在估计每个簇内的信号能量时采用的是多项式拟合的 方法。信号能量在传播过程中的变化是一个渐变的过程，而多项式拟合可以利用 信号能量在空间和时间上的连续性和渐变性来重构监测区域中信号能量的分布。 传感器网络中节点是随机分布的，且节点间有一定的间距，为了能重构如图2 2 所示的连续、光滑的信号能量分布， 1 3 对簇中节点所在区域做插值。公式( 2 2 ) 为采用的插值公式，其中的p ( x ，j ，) 是点( x ，y ) 处的插入值。 p q ，坊= p o + 】| b 、y + p 2 y 1 + p 3 x 七8 4 x y + p s 础z + | b 6 x z + p l x z y + p s x 2 y 2 q 公式( 2 2 ) 中，万= ( x7 x ) 1 x r 乏。这里万= ( 屈，届，孱) 7 ，而乞= ( z l ，z 2 ，乙) 第2 章目标计数问题 中的z f ，f 1 ，甩】是第f 个节点感知的信号能量值。 1 f l x = i i ： l 该拟合方法的参数万的最小平方误差为f ( 万) = ( x 万一乏) 7 ( x 万一z ) 。通过多 项式拟合，一个表述簇所覆盖区域的信号能量曲面的方程被构造出来。为了计算 该区域的信号能量总值， 1 3 】对该区域的信号能量求积分。在选取积分的范围时， 比较精确的方法是选取簇内节点的凸壳，或者选取簇内节点的v o r o n o i 区域，但 分布式条件下求解节点的凸壳或做v o r o n o i 划分需要一定的计算和通信代价。 1 3 】 选取簇内所有节点中最小的x ，y 值和最大的x ，y 值做为积分的范围，避免了过多 的计算和通信。 【13 对积分范围的选取方式比较简单，这导致一部分信号覆盖区域没有被纳 入积分。同时，传感器网络中节点的分布并不是非常密集，这会导致数据采样不 足。为了减小这些因素的影响， 1 3 】给作为参照的单个目标的信号能量总值赋了 权值。模拟实验表明，权值为0 7 时能正确估计目标个数。 【1 3 和 1 6 】相比，其成簇方法相似，在估计每个簇对应的目标个数时虽然也 是利用节点感知的目标信号能量，但采用了不同的方法。通过多项式拟合的方法 来重构区域内的信号能量曲面，再对曲面做积分得到区域内信号能量总值，其复 杂性比 1 6 】中对节点做v o r o n o i 划分要小很多。但【1 3 】的不足之处是为了能正确拟 合信号能量曲面，每个目标的信号能量必须相同：同时，为了通过信号能量总值 来估计目标个数，需要已知单个目标信号在区域中产生的信号能量总值。 2 2 3利用二元传感器的目标计数 如1 3 2 节所述，二元传感器是输出值只有1 和0 的传感器，其输出值1 代表在感知范围内存在目标，o 代表感知范围内没有目标出现。【1 1 】中详细讨论 了利用二元传感器定位和跟踪单个目标的精确度、限制和算法，提出对目标定位 的精确度与p r 加1 成反比，其中p 是传感器节点的密度，r 是传感器的感知半径， 而d 是监测区域的维度。 f 7 】则利用二元传感器来实现多目标的计数与跟踪。【7 】提出了几个定理。第 一，只有当每个目标之间的距离足够大，而不是只有某些目标间距离足够大时才 可能利用二元传感器准确的估计目标个数。这意味着给定节点的感知半径( 即目 标的影响半径) 尺，则每对目标的间距必须至少大于4 r ，才能正确估计目标个 数，并对每个目标定位，其定位误差是目( 1 p r 扣1 ) 。如图2 4 所示，能感知到目 标的节点分布在以目标为圆心，尺为半径的圆内，这些节点的感知范围的并集是 1 ：疆!；：i 以鬟弦 m 抛 鼽毋? 吞 ：鼍!迁 _ 巧 醴 ；h n s = 蜘 丑以 n 幻；如 篓；馥 n 始! 批 第2 章晷标计数目题 当目标间距较远，以致目标的影响范围互不重叠时，每个传感器节点只会感 知捌一个墨标。设感知到目标的节点数为n ，则可以对这些节点做一个划分 墨，s 鬈 ，使得| 墨| = ，且墨n 邑= 彩，f 毋，这里每个墨中的节点感知的是 同一个目标的信号，则划分后集合的数目k 即目标的个数。 感知到同一瞬标信号的节点在同一目标的影响范围内，即位于同一地理区 域；丽感知到不同霉标信号的节点位于不同霹标的影响范圈内，即位予不霹的地 理区域。这意味着当目标影响范围互不重叠时，以所有感知到目标的节点为顶点 构造的图中，同一集合中的节点间彼此连通，而位于不同集合中的节点间并不连 通。黢此，可以根据感知到星标的节点闻的连通状况来划分节点。如图2 ，6 所示， 目标a 和b 影响范围内的节点会分别被并入两个不同的集合中，而仅以这两个集 合中的节点为顶点构造的图中两个集合间不连通。 图2 6 目标相距较远时节点的划分 当目标相距较近，使得目标的影响范围踅叠时，在重叠区域中的节点会同时 感知到多个目标。此时，在这几个目标的联合影响范围内的节点彼此间是连通的， 于是这些节点被并入同一个集合中，这意味着集合的数目小于目标的个数，不能 用来估计晷标个数。如图2 7 所示，叠标轰和b 的影嚷范围重叠，则在矗和8 影响范围内的节点间彼此连通，被并入同一集合中。此时，一个集合对应了两个 目标。 1 4 圈2 。7 露标楣距较近辩节点酶划分 传感器节点无法判断目标间距的远近，因此划分后的节点集合对应单个或多 第2 章目标计数问题 个相距较远的目标。此时需要进一步利用节点感知的数据，通过节点间的协作来 估计集合对应的目标个数。 观察图2 2 中在监测区域内的信号能量曲面。由于信号相遇时其能量只是简 单叠加，因此当各目标的信号能量均相同时，在监测区域内对信号能量求得的曲 面积分与单个目标所产生的曲面积分成正比关系，比值即为区域内的目标个数。 【1 3 】采用多项式拟和充分利用信号在衰减时在空间和时间上的连续性和渐 进性来重构监测区域中信号能量曲面图，并利用插值的方法求得曲面积分。 1 6 的e b a m 则是用簇内节点感知的信号能量的加权和来近似表示区域内信 号能量值的积分值。连续的曲面积分能够用离散点的黎曼和去逼近，进一步推广， 在传感器网络中经过修正的各节点感知的信号能量之和可以近似为该区域内信 号能量值的曲面积分。 2 4 本章小结 本章首先描述了目标计数问题。之后本章详细介绍了当前在目标计数问题中 的研究进展，分析了相关算法的思想、实现、优势与不足。最后本章对已有算法 做了总结。 目前解决目标计数问题的方法在目标相距较远时能够很好的估计目标个数。 当目标相距较近时，利用二元传感器节点不再能有效估计目标个数，此时利用传 感器感知的目标信号能量仍能较好估计目标个数。但是仅仅利用信号能量要求目 标的信号能量相同且己知，并且抗噪声干扰能力不强。 第3 章算法可行性分析、思想与设计 图中可以看到当两个序列之间的滞后增加时，相关度可近似视为单调递减。对于 不超过o 1 2 秒的滞后，相关度至少为o 6 。 滞后的采样时间( 0 0 2 秒) 图3 3 信号的包络图3 4 滞后对信号包络间相关度的影响 3 1 2不同目标叠加影响范围内节点信号间相关性 如果不同的目标相互独立，它们发出信号的时间不同步，则一般来说不同目 标的信号序列相关度较小。如果不同目标的信号波形有差异，则信号序列的相关 度更小。 当节点位于多个目标的叠加影响范围内时，离它最近的目标的信号在该节点 处的能量最大，因而在该节点感知的信号中占主要成分。 考虑一个边长为1 0 0 米的正方形区域，传感器数为1 0 0 个，随机均匀分布。 实验中选取的两个目标的信号能量相同，影响范围均为4 0 米，且目标信号的包 络之间相关度为0 3 2 3 6 ，目标一的位置为( 4 0 ，5 0 ) ，目标二的位置为( 6 0 ，5 0 ) 。节 点的分布以及根据 1 6 的d a m 算法构造的簇如图3 5 所示。位于直线x = 5 0 左侧 的节点距目标一最近，视之为集合1 e f t ，位于直线x = 5 0 右侧的节点距目标二最 近，视之为集合r i g h t 。分别计算l e f t 和r i g h t 中的节点感知的信号的包络与 两个原始目标信号的包络之间的相关度，所得结果如图3 6 所示。 由图3 6 可见，1 e f t 集合中的节点感知的信号包络与位于左侧的目标一的 信号包络之间的相关度大于它们与位于右侧的目标二的信号包络之间的相关度， 而r i 曲t 集合中的节点正好相反。因此若根据节点感知的信号的包络与原始目标 信号的包络之间的相关度将节点分组，则l e f t 和r i g h t 应各自对应一个组，而 每个组均对应一个目标。 图3 6 中，两个组中节点按照它们与目标的间距升序排列，而这和节点感知 的信号包络与目标信号包络之间相关度的降序排列相吻合。这说明，距目标越近 的节点感知的信号与原目标信号的相关度越大，也就越能代表目标信号。因此， 在原始目标信号未知时可以用距目标最近的节点感知的信号来代表目标的信号。 第3 章簿法可行性分析、思想与设计 图3 5 两个目标得到的d a m 妒 叁锻蒹羹藿囊夯蘩萋茹些萋誉奏 裂薹。鞫羹霎两藤譬匣蓁嘭薹翼薪翳稔牦 鎏囊i 堇慧蓁囊羹垂摧蒌萋羹雾萋； l i l 猎型靠滔强净”懑羹薹再垮堂照慧；萋孺澌薹喜薹掣麦雾塞哺羹! 羹 漳啄绋饼鍪静盼醣醐针i l 零i 鬻霉稼疆甥薹型霪蓁蛊涮撰萎橥建交；剥澎豢鬈赫蓁耄毯霎雾私塑誉里 呙制鋈薹纠照黼塑；鬻酥薹。羹 5 0 次秒的 第3 章算法可行性分析、思想与设计 相关度最大。 ( 3 ) 在与给定目标最近的节点集合中距目标越近的节点感知的信号越能代 表目标信号，而距目标越近的节点感知的信号能量越大。因此节点感知的信号能 量越大，其距目标越近，其感知的信号也越能代表目标信号。 ( 4 ) 当一组节点感知的信号包络之间相关度较大，而它们与其他节点感知的 信号包络间相关度较小时，可以认为这组节点感知的信号的主要成分为同一目标 的信号。 综上所述，利用节点采集的信号序列之间的相关性对节点进行分类，将信号 相关性较大的节点归为一类并对应一个目标是可行的。而当节点感知的是多个目 标信号的叠加信号时，其信号序列与最近目标的信号序列间相关度最大。因此， 在混合信号的情况下仍能够根据信号间的相关度对传感器节点进行分类。 3 2 算法思想 由3 1 的分析可知，利用信号相关性估计目标个数是可行的。为了限制参与 相关性比较的节点范围，需要将节点分成不同的集合，使得每个集合对应单个或 多个相距较近的目标，而相关度计算仅限于集合内部的节点间。本文将同一集合 的节点用簇的拓扑结构组织起来，使得节点间的通信更加高效。集合内信号沿着 簇逐层传递，使得节点间信号相关度的计算有序，不会冗余计算。根据信号相关 性将节点分成不同的组后，由于每组分别对应一个目标，因此可以由各组节点协 同估计相应的目标位置。 本节将介绍本文算法的基本思想。首先是成簇算法的思想，之后是簇内根据 相关度将节点分组的思想。最后，将介绍根据各节点组估计相应目标位置的算法 思想。 3 2 1 分簇 本文采用的分簇算法为 1 6 中的d a m 算法。d a m 算法中父节点感知的信号能 量大于子节点感知的信号能量，由3 1 节的分析可知父节点感知的信号更能代表 目标信号。因此，d a m 簇的簇头感知的信号最能代表一个目标的信号。同时，d a m 是由感知到目标信号的节点构造的簇，这意味着簇的构造是动态的，能及时对目 标的变化做出反应。 d a m 簇中节点感知的信号能量的分布与目标信号传播时的衰减契合，因此也 满足了局部性，即一个簇对应的是单个或多个相距较近的目标。图3 7 所示是在 1 0 0 米x l o o 米的区域中有1 0 0 个节点和5 个目标时用d a m 算法形成的簇的二维 2 l 第3 章算法可行性分析、思想与设计 图形，黑色方块为目标，圆圈为节点，父子节点间由线段连接。图3 8 所示是相 应的簇中各节点感知的信号能量的三维图形。 图3 7d a m 簇的二维形状 图3 8d a m 簇的三维形状 3 2 2目标计数 当节点检测到多个目标的混合信号时，距节点最近的目标的信号在混合信号 中占主要成分。我们的仿真实验表明，当两个混合信号的相关度在0 7 以上时， 一般来说它们的主要成分来自同一目标信号，对应的两个节点应归入同一组中。 我们将这个临界值称为分组阀值。由3 。1 节的分析知，来自相同目标、经过衰减 与延迟的信号序列之间仍具有很大的相关性。因此根据信号间的相关性将节点分 第3 章算法可行性分析、思想与设计 组，使彼此间相关度超过分组阀值的节点归为一组，则组数即对应了目标的个数。 当节点稀疏时，为了能较好分辨目标，应当只将距目标较近的节点归入目标对应 的组，因此当节点密度减小时需相应提高分组阀值。 因为d a m 簇中父节点感知的信号能量大于子节点感知的信号能量，亦即父 节点距目标更近，所以父节点感知的信号比子节点感知的信号更能代表目标信 号，而簇头感知的信号最能代表目标的信号。基于以上原因，本文提出基于信号 相关性的两阶段算法s c b n ( s i 瓯a lc o 玎e l a t i o nb a s e dn u m e r a t i o n ) 。 第一阶段，簇头将自己检测到的信号序列发送给每个子节点，子节点计算父 节点的信号序列与自己检测到的信号序列的相关度。若相关度大于分组阀值，将 自己划为与父节点同组，并向其子节点转发父节点的信号序列。若相关度小于分 组阀值，表明自己检测到的信号与簇头节点检测到的信号不同源，节点丢弃父节 点的信号序列，向子节点发送自己的信号序列。这样，随着信号序列从簇头传播 到叶子节点，每个节点都将自己划入到某个组中，每组中检测到最强信号的节点 成为这个组的组长。 此时，每个目标均在簇中有了相应的节点组与之对应。然而，簇的树状结构 使得每个簇中节点只是与父节点计算相关度，而无法与自己的兄弟节点计算相关 度。如图3 9 示，目标一与目标二信号能量相同，距离较近，两目标影响范围内 的节点a 、b 和c 在一个簇中。节点a 因为距目标更近，感知的信号能量大于b 目标l 2 目标2 图3 9 两个组对应一个目标 和c 感知的信号能量，所以a 是b 和c 的父节点，而b 和c 是兄弟节点。在簇中 a 向b 和c 发送信号s 。b 距目标二更近，其感知的信号与a 发来的信号之间相 关度小于分组阀值，所以b 创建一个新组，自己作为组长向它的子节点发送b 感知的信号。c 与b 的情况相同。这样，目标二在簇中存在两个节点组与之对应。 出现上述情况的原因是信号仅在父子节点间传递，而兄弟节点之间的信息并 第3 章算法可行性分析、思想与设计 图3 1 1 利用s c b n 算法得到的节点分组图 3 2 3 目标定位 当目标相距较近以致目标的影响区域相互重叠时，难以对每个目标实现定 位，因此当前对目标的定位算法都是限于对单个目标或相距较远的多个目标定 位。 当目标的影响范围重叠时，本文s c b n 算法可将节点根据信号相关性分组， 使每个组均对应一个目标。这就意味着当目标相距较近时仍然可以通过组内节点 间的协同工作对目标定位。 本文考虑用组内节点的加权质心来定位对应的目标。公式( 3 3 ) 中z ( x ，j ，) 是 第f 个目标的位置，只是第f 个目标对应的节点组中的节点，s ，( x ，y ) 是该节点的 位置，罗是对节点组中所有节点求和。 驰川：靴 ( 3 3 ) 厶lj 在计算节点组的加权质心前需要更新每个节点的组信息。在s c b n 算法中， 同一目标在簇的不同分支上对应的节点组之间不断合并，而被合并组中的节点并 没有更新自己的组信息。因为在s c b n 算法结束前节点组是动态变化的所以只能 等算法结束后才能更新节点的组信息。 为了正确更新组信息，在s c b n 中当某节点将组g 。并入组g 厅时，会保留组 标号q 和一个映射关系 。 第3 章算法可行性分析、思想与设计 当s c b n 算法结束后，簇头将保留的组标号集合、删除的组标号集合以及相 应的映射关系发送给子节点。子节点的组标号若在父节点删除的组标号集合中， 则根据父节点发来的映射关系更新子节点的组标号。 在节点继续向下发送自己存储的这两个集合和相应的映射关系前需要根据 父节点发来的信息更新这些信息。若子节点保留的组标号在父节点删除的组标号 集合中，则根据父节点发来的映射关系更新自己保留的组标号集合、删除的组标 号集合与相应的映射关系。例如，在父节点处组g 。并入组g 。，而子节点中g 。是 保留的组标号，则子节点将g 。加入保留的组标号集合，将g 。转移到删除的组标 号集合，并建立映射关系 。在更新时可能出现嵌套合并组的情况。 例如在上例中，若子节点同时有映射关系 ，则此映射关系改为 。 当叶节点完成更新后，每个节点向自己所在组的组头节点报告自己的位置和 感应到的信号能量，由组头节点根据( 3 3 ) 式估计目标位置，再将该位置发送给 簇头。 3 3 算法设计 3 3 1分簇算法设计 节点通过参与簇头选举来构造簇。初始时，当节点感知的信号能量大于给定 阀值时即参与簇头选举，这样根据不同的监测任务可以设定不同的阀值，同时可 以控制目标的影响范围。参与簇头选举的节点发送自己感知到的信号能量和自己 认可的簇头信息( 初始时自己即簇头) 给邻居节点，邻居会将其与自己已获知的 信息作比较。若消息发送方感知的信号能量大于接收方感知的信号能量，且发送 方认可的簇头信号能量大于接收方认可的簇头信号能量，则接收方将发送方视为 自己的父节点，并将簇头标记设置为发送方的簇头标记。在完成父节点与簇头信 息的更新后，消息接收方会更新消息中的相关信息，并转发该消息。若不满足上 述条件，则消息接收方会抛弃所接收的消息。这样，在算法运行时消息只会从感 知到高信号能量的节点流向感知到低信号能量的节点。在消息被不断转发的过程 中，各节点的父节点和簇头信息会被不断更新，最终形成的簇中父节点感知的信 号能量大于子节点感知的信号能量，而每个簇中只会有一个信号能量峰值，即簇 头感知的信号能量。 在d a m 算法中，每个参与簇头选举的节点保存的信息为当前认可的簇头标号 1 e a d e r i d 和簇头感知的信号能量m a x p r h e a r d ，自己的标号m y i d 和感知的信号能 量m y p r ，以及父节点标号p a r e n t i d 。 第3 章算法可行性分析、思想与设计 在算法进行时节点间传递的消息中包含发送方认可的簇头标号m a x i d 和簇 头信号能量f 1 1 a x p r ，发送方自己的标号t r a n s i d 和自己感知的信号能量t r a n s p r 。 算法的伪代码描述如下： 算法描述如下： 1 在初始阶段 i f ( m y p r t h r e s h 0 1 d ) 认为自己即簇头，并设定相应值及广播相应消 息 m a x p r h e a r d = m y p r ： l e a d e r i d = m y i d ： m = c r e a t e m e s s a g e ( ) ： m m a x p r = m t r a n s p r = m y p r ： m m a x i d = m t r a n s i d = m y i d ： b r o a d c a s t ( m ) ： 2 当节点从邻居处收到消息m i f ( m m a x p r m a x p r h e a r d m t r a n s p r m y p r ) m a x p r h e a r d = m m a x p r ：更新存储的簇头信息 1 e a d e r i d = m m a x i d ： m y p a r e n t = m t r a n s i d ：更新父节点信息 m t r a n s p r = m y p r ：更新消息中的转发节点信息 m t r a n s i d = m y i d ： b r o a d c a s t ( m ) ： e 1 s ed r o p ( m ) ： 若消息传播方向与信号传播方向相反则抛弃 最终簇头产生的消息会被发送至簇内每个节点，这时算法结束。形成的簇中仅有 一个信号能量峰值，且父节点感知的信号能量大于子节点感知的信号能量。 3 3 2目标计数算法设计 在第一阶段，当构造好d a m 簇后，簇头创建一个组，自己担任组长，并将簇 头感知的信号向子节点传送。每个收到父节点发来的信号的节点会计算收到的信 号与自己感知的信号之间的相关度，若大于分组阀值则将自己归入父节点所在的 组，并向子节点转发父节点发来的信号。这一设计使得最能代表目标的信号沿着 簇被不断往下转发，使得与该目标最近的节点被陆续并入相应的组中。 若信号间的相关度小于分组阀值，则当前节点不属于父节点所在的组，不再 蓁3 牵雾渡西嚣茬籴爨、恶慧与襄嚣 向下转发父节点发来的信号。此时，当前带点与另一目标煅i 履；由于空闻相关性 翁蘸霆，娄蓠节点熬予萋熹也缝鼗冬燕委蠢袋避。透羹簇中父繁矗