无线传感器网中目标定位算法的研究

作者简介： 孙学斌（ ， 男， 博士研究生， 研究方向为自组网与无线通信。周正（ ， 男， 教授， 博士生导师， 研究领域为信号处理、 无线通信 &864= ） &8#4= ） 技术。
&%! !""#$%
计算机工程与应用
表示。 每个节点与其任一邻节点之间都存在一条双向的无线链 路，这样无线传感器网就可以抽象成为一个无向图模型 ! （ "， ， 其中 # 表示所有无向无线链路边的有限集合。笔者定义一 #） 系列相连的横贯整个网络的链路集合为“ 切” 。 假定客户节点知道整个网络的拓扑结构和各节点的位置， 客户节点因为无线收发器的功率限制， 也只能与邻近的传感器 节点通信。当客户节点需要确定某目标的位置时， 向传感器网 络发送查询消息。 传感器节点将采集到的目标的原始物理量信 号转化成该目标的逻辑标志符， 用 $%& 表示。客户节点发出的 查询消息的构成为： 〈 〉 ， 其中 $%& 是给定的， ’： $%& ， (， )（ (， $%& ） 而 (， 即： 期 ) 都是未知的。 ’ 查询标志符为 $%& 的目标的位置， 望的返回结果是传感器节点的标志符 ( 和 ( 监测到该目标的 时 间 )（ 。 用 户 感 兴 趣 的 结 果 是 )（ ， (， $%& ） (， $%& ） *) （ +， $%& ） 当没有发现目标时， 的返回值都 + !( ， +， ( "" 。 ( 和 )（ (， $%& ） 是 ,-..。 该文要解决的目标定位问题可以表述为： 设计一种定位算 法，通过向无线传感器网发送查询消息 ’ ： 〈 〉 $%& ， (， )（ (， $%& ） 来获取特定目标的位置， 使得完成目标定位过程中传输的消息 数量最小化， 以增强节点资源受限的无线传感器网的实用性。
图& 算法执行过程图例
%$!
搜索目标拖尾
算法的第一步是搜索目标拖尾。 客户节点首先选择一个切
% 基于追踪的目标定位算法 %$& 算法的基本思想
该文的算法需要利用目标的运动轨迹进行追踪， 因此称之 为基于追踪（ 的目标定位算法。 算法基于这样一 ’()*+,-./0)123 ） 个事实：当目标在无线传感器网所覆盖的地理区域中移动时， 其运动轨迹在时间和空间上都是连续的。 一旦目标进入该地理 区域， 就已经处于某传感器节点的监测范围中； 在目标离开某 节点监测范围的同时，立即进入了其邻节点的监测范围中， 直 到目标离开传感器网所覆盖的地理区域。 令 每 个 节 点 都 记 录 下 曾 监 测 到 的 目 标 的 $%& 和 监 测 时 间 （ 如果曾多次监测到， 则只记录最近一次的时间） 。 这样， 传感器 网就记录了每个目标的运动轨迹，这里称该轨迹为目标的拖 尾。笔者注意到传感器节点的存储空间有限， 如果曾监测到的 目标过多， 可能无法保存所有目标的信息。 对此， 笔者采取自适 应覆盖技术： 当有新的监测目标出现时， 自动覆盖最早记录的 目标信息， 这样的后果是被覆盖目标的拖尾被缩短了。该文的 定位算法利用目标的拖尾对目标进行追踪定位， 下面是算法的 基本框架： 算法功能： 对无线传感器网中的特定移动目标进行定位。 输入 指定目标的逻辑标志符。 $%& ： 输出 最后一个监测到目标的传感器节点的标志符； (： 节点 ( 监测到目标 $%& 的时间。 )： 算法步骤 （ 找到一个曾监测到目标 $%& 的传感器节点， 即： 找到目 &） 标 $%& 的拖尾； （ 沿着 $%& 拖 尾 进 行 追 踪 ， 直到拖尾顶端， 即 $%& 所 在 的 !） 位置； （ 给客户节点返回应答， 即： 返回拖尾顶端节点的标志符 %） 。 ,%& 和 )（ ,%& ， $%& ） 图 & 用直观的方式演示了算法的执行过程。 接下来分别对 算法执行的各个步骤进行详细讨论。
的 缺乏传统的基础网络设施（ ,-./0-/. 、 12( 和 移 动 通 信 网 等 ） 支持。 在无线传感器网的许多应用领域里， 往往需要对监测区域 中的特定物理目标进行跟踪和定位。比如抢险救灾中， 灾区中 布置的传感器网能够追踪医护人员的位置； 战争中军队可以在 可能被破坏） 的 阵地上布置传感器网， 用 于 追 踪 无 12( 支 持 （ 士兵、 车辆等的位置； 在禁入地区可以用来监测和追踪闯入者*#+。 该文着重于为无线传感器网中物理目标定位问题设计一种实 用的解决方案。 由于传感器节点资源受限的特点， 解决上述问题具备了相 当的挑战性。尤其是各节点采用容量有限的电池供电， 而要在 几年内将目前的电池可供电时间提高 %"3都是很困难的 *4+。一 旦电池耗尽， 传感器节点失效后就会在监测区域中形成监测盲
5+ ， 因此应尽量减少传输的消息数量。 另外， 由于节点无线 因素 *#，
处理和无线通信能力的小体积、 低成本的传感器节点构成的自 通常用来监视一个特定的地理区域。近年来在微电 治 网 络 *!+， 子、 无线通信研究领域的进展使生产和推广这种传感器成为现 实。网络中的每个节点独立地检测周围的环境， 然后互相协作 实现 复 杂 的 功 能 ， 譬如闯入检测、 目标追踪与定位、 环境监测、 遥感等。该网络可以应用于地球物理学（ 例如地震监测） 、 军用 这些领域通常 系统、 抢险救灾、 交通监测、 生物学研究 等领域，
&
引言
*&+ 无线传感器网（ 是由大量的集成了传感、 数据收集、 ’()）
区。这些失效节点往往难以更换， 特别是当网络布置在无人区 时。这样发展的后果就是网络的覆盖范围、 网络寿命和实用性 都大大降低了。 因此， 在设计定位问题解决方案时， 能源节省是 必须考虑的因素。 研究发现消息的无线传输是消耗能源的主要
*%+
收发器的带宽一般都比较小， 节省网络带宽也变得非常重要。 无线传感器网中传统的数据传递方法是各节点不断地把 采集的原始数据传送给一个数据处理中心。然而， 由于数据量 太大， 节点电源将很快消耗殆尽。近几年许多学者对如何减少 传送描述性数 传送数据量做了一些研究， 比如本地数据压缩 *#+、
8+ 据代替实际数据 *6+和传送查询消息 *7， 等。该文采用传输查询消
基金项目： 电子工业发展基金资助项目（ 编号： !"""&"பைடு நூலகம்6 ）
息的方法。网络外部的某客户节点向网络发送查询消息， 网络 在完成消息处理后给客户节点返回应答。 通过精心设计消息处 理算法， 该方法取得了很好的效果。
!
网络模型及问题的表述
该文用 ! 9:" &， …， …， " !， " #， " $; 表示分布 在 某 一 特 定 地 理 区
/9#,%$&,： HV@B W?W/0 W0JWJB/B ? .?0O/. AJU?.@-O ?AOJ0@.V> .J AJU?./ ? .?0O/. >JQ@-O .V0JCOV ? O/JO0?WV@U ?0/? C-T/0 BC0Q/@AA?-U/ JS ? I@0/A/BB B/-BJ0 -/.IJ0K$HV@B ?AOJ0@.V> S@-TB ? B/-BJ0 -JT/ .V?. V?B T/./U./T .V/ .?0O/.， ?-T .V/- CB@-O AJU?A >/BB?O/B E/.I//- -/@OVEJ0@-O -JT/B .J SJAAJI .V/ .0?@A JS .V/ .?0O/.$HV@B W?W/0 @>WA/>/-.B .V@B ?AOJ0@.V> ?-T UJ>W?0/B @. I@.V ?- JW.@>@X/T SAJJT =E?B/T AJU?.@-O ?AOJ0@.V>$(@>CA?.@J- 0/BCA.B BVJI .V?. .V@B ?AOJ0@.V> /SS/U.@Q/AR 0/TCU/B .V/ >/BB?O/ .0?-B>@BB@J-B， UJ-B/0Q/B E?-TI@T.V ?-T /-/0OR ， ?-T UJ-B/YC/-.AR /-V?-U/B .V/ W0?U.@U?E@A@.R JS 0/BJC0U/=A@>@./T I@0/A/BB B/-BJ0 -/.IJ0KB$ ;"<5(%=#： ’@0/A/BB (/-BJ0 )/.IJ0KB， LJU?.@-O GAOJ0@.V>， <-/0OR ZJ-B/0Q?.@J-
域 % 中的无线传感器网的所有 $ 个节点。每 个 节 点 " # 都 拥 有 能够对在范围 (（ 内的目标进行 一个全网唯一的标志符 &#’ ， " #） 监测， 且满足
!
#)$ #)&
令传感器节点采用 (（ " #） )% 。为了方便讨论，
栅格分布 *&"+。离节点 " 最近的四个节点为其邻节点， 用 &*+, （ "）
文章编号 &""!=7%%&=（ !""# ） "%="&%!="%
!"#"$%&’ () *$%+", -(&$,.)+ /0+(%.,’1# .) 2.%"0"## 3")#(% 4",5(%6#
37) 87"9.) :’(7 :’")+ （ ’@0/A/BB )/.IJ0K L?EB， M/@N@-O P-@Q/0B@.R JS 2JB.B ?-T H/A/UJ>>C-@U?.@J-B， M/@N@-O &""765）