CAJ | 학술논문

针对分布式 MDS-MAP 算法的不足，提出了一种基于图刚性理论的无线传感器定位新算法 MDS-MAP (GR)。算法利用图的刚性理论，确定网络中的所有刚性子区域，然后利用合并定理将刚性子区域进行扩展，最后对合并得到的刚性区域利用 MDS-MAP 算法和锚节点实现网络中节点的大规模定位。算法尽可能对刚性区域进行合并，节省了执行 MDS-MAP 算法的次数，提高了执行效率。通过在不同拓扑结构的无线传感器网络中进行了仿真实验，说明了提出的算法能有效定位不同半径下网络中90%以上的节点，另外，新方法比现有方法在定位成功率上提高了4%～5%，并且定位精度提高了2%～3．5%左右。算法适用于大规模无线传感器网络中的快速定位。
침대분포식 MDS-MAP 산법적불족，제출료일충기우도강성이론적무선전감기정위신산법 MDS-MAP (GR)。산법이용도적강성이론，학정망락중적소유강성자구역，연후이용합병정리장강성자구역진행확전，최후대합병득도적강성구역이용 MDS-MAP 산법화묘절점실현망락중절점적대규모정위。산법진가능대강성구역진행합병，절성료집행 MDS-MAP 산법적차수，제고료집행효솔。통과재불동탁복결구적무선전감기망락중진행료방진실험，설명료제출적산법능유효정위불동반경하망락중90%이상적절점，령외，신방법비현유방법재정위성공솔상제고료4%～5%，병차정위정도제고료2%～3．5%좌우。산법괄용우대규모무선전감기망락중적쾌속정위。
In order to solve the shortage of distributed MDS-MAP localization algorithm, this paper presented a new localiza-tion algorithm for wireless sensor network based on graph rigidity.Firstly, the presented algorithm utilized graph rigidity theory to determine all rigid sub-regions in network.Secondly, it used a merging theory to merge these rigid sub-regions.Finally, it used the MDS-MAP algorithm and anchor node to localize network nodes during these merged regions with a large scale.Be-cause the proposed algorithm merged all rigid sub-regions as soon as possible before running the MDS-MAP algorithm, it re-duced the run times of MDS-MAP efficiently and enhanced the proposed algorithm’s performance.Through the simulation ex-periments in wireless sensor network with different topology structure, the results show that the proposed algorithm can effi-ciently localize more than ninety percent nodes with different communication radius.In addition, compare with previous meth-od, the success rate of localization presented algorithm is improved 4% ~5% and the accuracy is improved 2% ~3.5%.The presented algorithm is compatible to localize nodes in large scale wireless sensor networks.