改进APIT节点定位系统软件-软件文档.doc

改进APIT节点定位系统软件V1.0 软件文档 中国矿业大学 2011年2月目 录 1 运行环境 1 2 改进APIT节点定位算法 1 2.1 APIT原理 1 2.2 APIT步骤 1 2.3 网格扫描法 2 2.4 APIT的改进 4 2.4.1 引入计数器对APIT算法进行改进 5 2.4.2 扩大邻居节点的定义范围 5 2.4.3 迭代思想（unknown-to-anchor） 5 2.5 改进APIT定位算法流程 5 2.6 基于改进APIT算法的重心扫描法 7 3 改进APIT节点定位算法仿真平台 8 3.1 真实事件在仿真中的特殊处理 9 3.1.1 节点的真实坐标与估计坐标 9 3.1.2 分布式算法在单机上的实现 9 3.1.3 节点通信机制 10 3.1.4 接收信号强度的表示 10 3.2 核心数据结构 10 4 软件模块设计 12 4.1 文档模块 13 4.2 显示模块 13 4.3 控制模块 14 4.4 关键算法实现函数： 16 5 软件使用说明 18 5.1“显示模块”操作说明 18 5.2 节点操作 18 5.3 “场景模式”操作 19 5.4 “操作模式选择”操作 20 5.5 “定位步骤”操作 20 6 技术支持 22  1 运行环境Microsoft Visual C++ 6.0。 2 改进APIT节点定位算法 2.1 APIT原理 APIT利用网络中相对较高的节点密度来模拟节点移动，利用无线信号的传播特性来判断是否远离或靠近锚节点，通常在给定方向上，一个节点距离另一个节点越远，接收到的信号就越弱。邻居节点 通过交换各自接收到信号的强度，判断距离某一信标节点 的远近，从而模仿PIT中节点移动。 APIT理论：如果M节点不存在同时远离或接近于A，B，C的邻居节点，则判定M位于ABC内部，否则的话，判定M位于ABC外部。 2.2 APIT步骤 APIT定位具体步骤：收集信息：未知节点收集邻居锚节点的信息，如位置、标识号、接收到的信号强度等等，邻居节点之间交换各自接收到的信标节点的信息；APIT：测试未知节点是否在不同的信标节点组成的三角形内部；计算重叠区域：统计包含未知节点的三角形，计算所有三角形的重叠区域；计算未知节点位置：计算重叠区域的质心位置，作为未知节点的位置。图1是APIT节点定位算法流程图： 图1 APIT节点定位算法流程图 2.3 网格扫描法 网格扫描算法是传统的APIT的定位方法。对于每一个参考节点，根据检测到的锚节点，采取不同的组合三角形，进行定位，判断节点在三角形的内部还是三角形的外部，然后不断重叠节点在三角形内的区域，区域会越来越窄，最后逼近到一个相对很小的区域，再取这个图形的质心作为未知节点的估计位置。 图2 网格扫描法原理示意图 在图2中，我们把这个侦听区域划分成许多网格，网格阵列代表节点可能存在的最大区域，每个网格的初始值为0。如果判断出节点在三角形内，相应的三角形所在的网格区域的值加1；同样，如果判断出节点在三角形外，相应的三角形所在的网格区域的值减1。 网格扫描算法的流程图如图3所示： 图3 网格扫描算法流程图 2.4 APIT的改进 从定位精度角度讲，APIT定位流程又可以分为两大阶段：第一阶段是每个未知节点通过锚节点和未知节点广播消息来收集周围未知节点和锚节点的信息，然后通过APIT测试来建立自己的支持数据集；第二阶段是调用相应的扫描算法来对支持数据集进行扫描，并最终获得待定位节点的估计位置坐标。 第一阶段，支持数据集的纯度主要取决于APIT测试算法；第二阶段，最终定位精度与扫描算法和InToOut错误与OutToIn错误直接相关。为了提高最终的定位精度，我们通过对APIT测试算法或扫描算法寻求相关的改进或是创新来实现。 2.4.1 引入计数器对APIT算法进行改进 关于APIT定位算法的性能改进主要是从APIT算法的两种错误和节点定位数目的两个方面出发考虑的我们将其命名为改进的APIT定位算法。. 对于解决APIT定位算法固有的两种错误：InToOut错误和OutToIn错误，提出了在节点内部设置计数器的方法来尽量降低两种错误产生的概率，具体做法是：在节点内部设置两个计数器CounterA和CounterB,对于一组锚节点组成的三角形，根据邻居节点的信标交换，运用APIT定位思想进行判决，如果根据接收信号强度SS判决未知节点在锚节点组成的这个三角形内部的邻居节点的数目是M，计数器CounterA等于M;如果判决未知节点在锚节点组成的这个三角形外部的邻居节点的数目是N，计数器CounterB等于N;如果MN,则我们认为未知节点在这三个锚节点组成的三角形的外部；如果MN,则我们认为未知节点在这三个锚节点组成的三角形的内部。然后采用相同的方法穷尽未知节