《分布式无线传感器网络定位算法MDSMAPD马震》由会员分享，可在线阅读，更多相关《分布式无线传感器网络定位算法MDSMAPD马震（6页珍藏版）》请在金锄头文库上搜索。
1、2008 年 6 月 Journal on Communications June 2008 第 29 卷第 6 期 通 信 学 报 Vol.29 No.6分布式无线传感器网络定位算法 MDS-MAP(D) 马震，刘云，沈波 （北京交通大学 通信与信息系统北京市重点实验室，北京 100044） 摘 要：针对无线传感器网络的定位问题，提出了一种分布式的算法 MDS-MAP(D)，明确给出了节点相对坐标计算和局部网络融合的过程，并对算法进行了计算复杂性分析和仿真。MDS-MAP(D)以分布式节点分簇为基础，利用网络的连接关系，在不需要高精度测距技术支持的条件下对节点坐标进行估计，减小了节点定位的计
2、算复杂度和能量消耗。分析与仿真结果表明，算法的计算复杂度由3()O N下降到2(),O NmmN。Ordinal MDS算法如下13： 1) 设定l中各节点的初始坐标为任意值，即 |( )iivNB l=x，其中ix表示节点iv 在2R 中的行向量。 2) 计算每一对节点间的距离 T()() ,rsrsrsdrs=xxxx (1) 3) 用 PAV 算法和rsl计算与rsd 对应的差异值rsd。 4) 求 Stress1 22()1rsrsrsddStressd= (2) 如果1Stress，算法结束，即为局部网络 l 的节点坐标集合，否则执行 5)。 5) 根据下式计算各节点的新坐标 *(
3、),(1/)()1srrrsrssr vNB l s rddM=+xxxx (3) 60 通 信 学 报 第 29 卷 其中，为步长因子，M为( )NB l的节点个数。 6) 更新，即令*ii=xx，转到2)。 3.4 融合算法与绝对坐标 设, r l为两个局部网络，如果( )( )NB rNB l包 含3个以上的节点，使用下式的变换把( )NB l中的节点坐标变换到r的坐标系统中去 ()rlosR=+xxx (4) 其中，s为缩放因子，()R为旋转变换，0x为平移变换。以下利用文献14中给出的方法分别求出s、 ()R和0x，从而把局部网络l融合到r中。 设E为( )( )NB rNB l中的
4、节点在r中的坐标矩阵(每行一个节点)，其第i个行向量用,r ix表示；S为( )( )NB rNB l中的节点在l中的坐标矩阵，, l ix为 第i个节点的行向量；D为( )( )( )NB lNB rNB l中的节点在l中的坐标矩阵。假设E与S中分别有n个 节点。 首先将r与l中节点的坐标扩展到3维空间， 并使第3维的坐标值全部为1。 令r与l的中心点分 别为 , 1111,nnrr ill i iinn=xxxx (5) 设,r ir irl il il=xxxxxx，s由下式给出 22,11nn r ir iiis=xx (6) E与S的协方差矩阵可表示为 T, 1nxxxyxzl iy
5、xyyyzr i izxzyzzCCC CCC CCC= = Cxx (7) 其中，,11,nn xxl ir ixyl ir iiix xxy=CC。由C计算矩阵U xxyyzzyzzyzxxzxyyxyzzyxxyyzzxyyxzxxzzxxzxyyxxxyyzzyzzyxyyxzxxzyzzyxxyyzzCCCCCCCCCCCCCCCCCC CCCCCCCCC CCCCCCCCC+ +=+ +U (8) 计算U的最大特征值对应的特征向量m 0123(,)mqq qq= 则旋转变换矩阵可由下式计算 2222 0123120313022222 2103012323012222 3102320
6、101232()2() 2()2() 2()2()qqqqq qq qq qq q q qq qqqqqq qq q q qq qq qq qqqqq+ =+ +R (9) 平移变换为 TorlR=xxx (10) 由式(4)、式(6)、式(9)、式(10)，就可以把D变 换到r的坐标系中，如式(11)所示。 ToFI=+DRx (11) 其中，I为与D具有相同行数的全1列矢量。 当一个WSN中有3个以上的锚点时，用上述 方法可以将WSN的相对坐标转换到锚点所在的绝 对坐标系统中去。此外，融合后不再需要对节点的 坐标进行优化调整。 4 分析与仿真结果 为了便于把本文提出的MDS-MAP(D)方
7、法与 文献6,8中给出的基于MDS的定位方法比较，这 里把工作在Range-Free环境下的基于Ordinal MDS 的MDS-MAP称为MDS-MAP(O)6， 把在此基础上 的改进方法称为MDS-MAP(P,O,R)8。 设具有N个节点的WSN，可以分为M个局部网 络，平均每个局部网络中有m个节点，2个重叠的局 部网络的共同节点数为n， 差异节点数为k。3.3节给 出的局部网络节点定位方法中，一次迭代的步骤1) 和6)的计算复杂度为( )O m，步骤2)5)的复杂度为2()O m。整个算法的多次迭代的计算复杂度为34() ()O mO m。3.4节给出的融合算法中，式(5) 式(7)的复
8、杂度为( )O n；式(8)和式(9)的复杂度为(1)O；求最大特征值的乘幂法计算时间为2()O n，这 里U矩阵是固定的44矩阵，因此复杂度为(1)O； 式(11)的复杂度为( )O k， 由于nkm+=， 因此最坏情 况下， 一个局部网络融合到另一个的复杂度为( )O m。 综合以上分析，MDS-MAP(D)方法的步骤1)(3.1节) 的计算复杂度为32()()O MmO Nm=；步骤2)的复杂度为34() ()O MmO Mm；最坏情况下，步骤3)的复杂度为(1) )()O MmO N=；步骤4)的复杂度为()O N。 由于MDS-MAP(D)把一个WSN分成多个局部 网络， 与MDS-
9、MAP(O)和MDS-MAP(P,O,R)中每个 节点都需要计算最短路径相比，计算复杂度由3()O N下降到了2()O Nm，这里m比N小很多。在 局部网络融合方面，MDS-MAP(D)最坏情况下的计 算 复 杂 度 为()O N， 优 于MDS-MAP(P,O,R)的3()O K N，其中K为节点的平均邻居数量。 本文结合GlomoSim和matlab对MDS-MAP(D) 以及MDS-MAP(O)和MAP(P,O,R)进行了仿真。仿第 6 期 马震等：分布式无线传感器网络定位算法 MDS-MAP(D) 61 真区域为一个10m10m的矩形区域，随机均匀部 署100个传感器节点。为比较通信障
10、碍对算法的影 响，还对C型网络进行了仿真。图1给出的是平均 连接度为10时的矩形网络和C型网络的连接图。 图 1 仿真中的网络结构 表1给出了不同的节点通信半径条件下， 分簇算 法对上述矩形网络进行局部网络划分的结果。 从结果可知， 分簇算法显著减少了局部网络的数量。 令K表 示节点的直接邻居的平均数量，由分簇算法可知，在 分簇阶段，最坏的情况下一个节点需要发送（包括转发）2K+条消息。由文献8可知，在没有分簇机制 的条件下，为完成局部网络融合，每个节点至少需要发送（包括转发）1K+条包含局部网络信息的消息。 分簇算法的通信能耗与不包含分簇机制的局部网络 融合过程的通信能耗大体相当。 但由上述
11、对算法复杂 性的讨论可知， 分簇算法的引入降低了节点定位的计 算复杂度，因而减少了定位计算的能耗。 表1 分簇算法的仿真结果 通信半径/m 2.0 2.4 2.6 3.0 3.4 3.8 局部网络数 7 6 5 4 3 3 图2所示为矩形网络中各算法的仿真结果。从 结果可以看出，MDS-MAP(D)在网络连接度大于10 时， 定位误差下降较快， 定位精度优于MDS-MAP(O) 方法。此外，随着锚点数量的增加，MDS-MAP(D) 比MDS-MAP(P,O,R)的定位精度有小幅度提高，约 为1%3%。 图3给出了C型网络上的仿真结果。 结果显示 网络中存在障碍时，MDS-MAP(D)的定位误差
12、明显 小于MDS-MAP(O)方法， 在不同环境下的误差平均 值与MDS-MAP(P,O,R)方法相当。 图 2 矩形网络中不同定位方法的比较 图 3 C 形网络中不同定位方法的比较 图4所示为算法对节点位置的估计，其中表 示估计位置，线段指向节点的实际位置，表示锚 点位置。从图中可以看出位置估计误差分布与锚点 位置无关，这与文献8的结论一致。 图 4 算法对节点位置的估计 62 通 信 学 报 第 29 卷 5 结束语 本文针对WSN节点的定位问题，提出了一种 分布式的算法MDS-MAP(D)， 并明确给出了局部网 络融合的方法。该方法可以有效降低节点定位的计 算复杂度，减少节点定位计算的能
13、耗，能适应网络 中障碍物的干扰，并提供较高的定位精度。 致谢：感谢张振江老师参与讨论，并给出具有 建设性的建议。特别向对本文提出宝贵意见和建议 的审稿专家表示衷心感谢。 参考文献： 1 任丰源, 黄海宁, 林闯. 无线传感器网络J. 软件学报, 2003, 14(7): 1282-1291. REN F Y, HUANG H N, LIN C. Wireless sensor networkJ. Journal of Software, 2003, l4(7): l282-l291. 2 MAO G, FIDAN B, ANDERSON B. Wireless sensor network l
14、ocal-ization techniquesJ. Computer Networks, 2007,51(10): 2529-2553. 3 王福豹, 史龙, 任丰原. 无线传感器网络中的自身定位系统和算法J. 软件学报, 2005,16(5): 857-868. WANG F B, SHI L, REN F Y. Self-Localization systems and algorithms for wireless sensor networksJ. Journal of Software, 2005, 16(5): 857-868. 4 BACHRACH J, TAYLOR C. Lo
15、calization in Sensor Networks in Handbook of Sensor Networks: Algorithms and ArchitecturesM. USA: Wiley, 2005. 5 SAYED A, TARIGHAT A, KHAJEHNOURI N. Network-based wire-less location: challenges faced in developing techniques for accurate wireless location informationJ. IEEE Signal Processing Magazine, 2005, 22(4): 24-40. 6 SHANG Y, RUML W, ZHANG Y, et al. Localization from mere con-nectivityA. Proc of ACM MobiHocC. Annapolis, MD, NY, 2003. 201-212. 7 SHANG Y, RUML W, ZHANG Y. Improved MDS-based localizationA. Proc of IEEE InfocomC. Hong Kong, China, 2004
