A Hierarchical MDS-based Localization Algorithm for Wireless Sensor

A Hierarchical MDS-based Localization Algorithm for Wireless Sensor

Networks

Gwo-Jong Yu*

Department of Computer and Information Science Aletheia University, Tamsui, Taipei, Taiwan

yugj@email.au.edu.tw

Shao-Chun Wang

Department of Computer and Information Science Aletheia University, Tamsui, Taipei, Taiwan

yugj@email.au.edu.tw

Abstract

In many applications of wireless sensor networks, location information is very important. Conventional lo-cation information comes from manual setting or the GPS device. However, manual location setting takes time, and GPS location setting entails high device cost as well as large device size. Furthermore, GPS can not operate indoors. Neither approach is feasible for the localization of wireless sensor net-works. In this paper, an accurate and efficient localization algorithm based on multidimensional scaling (MDS) in a hierarchical network envi-ronment is proposed. Through localized computation of multidi-mensional scaling within a cluster, the computa-tion overhead can be distributed to each cluster. On the other hand, MDS-based localization approach requires the estimation of the multihop distance. By re-stricting the multihop distances within a cluster, the proposed lo-calization algorithm is more accurate and can operate in non-convex network environments. Experimental results revealed that the proposed HMDS localization algorithm outperformed the MDSMAP algorithm in terms of ac-curacy.

Index Terms:localization algorithm, multidimensional scaling, hierarchical network.

1. INTRODUCTION by providing location information [3-4, 8-10].

A wireless sensor network [1] comprises of a Computing location information heavily de-large number of wireless sensor nodes. Usually, a pends on the deployment of wireless sensor networks. wireless sensor network has high density and is ran-Deployments of wireless sensor net-works can be

domly deployed. For example, an aircraft can have a roughly categorized into manual settings, GPS-based large number of wireless sensor nodes and scatter approaches, and localization algorithms. It is not them over a forest. With location information, the practical to manually set sensor location, because it is efficiency of cooperative computation can be further too time-consuming and expensive. For the enhanced through high performance geographic GPS-based localization method, the current/existing routing protocols [2]. The location information does GPS component is too big to fit into a tiny wireless not only expand application scenarios, but also en-sensor node. Another drawback is that GPS can not

hances performance of network protocols. In many be used in indoors. Using a localization algorithm to applications, such as environmental monitoring, dis-com-pute the location of each sensor is a promising

aster detection, and battlefield monitoring, location approach. Some localization algorithms require information is vital. Computing location information landmarks or anchor nodes which locations are al-with high accuracy and low cost is, therefore, a criti-ready known. Locations of sensor nodes can be cal research issue. computed with the localization algorithm. Shang et al.

If location information is available in the event proposed the MDS-MAP [8] localization algorithm detection of a sensor node, operators can accurately using multidimensional scaling (MDS) to compute send commands to the target location. For example, the coordinates of all nodes accord-ing to the relative in the application of forest fire detection, a fire truck distance between the nodes. Operations of needs accurate location using a wireless sensor node. MDS-MAP include the following three steps. Without location information, the availability of de-1) Computation of Distance Matrix,

tected data is limited. Then, if a sensor knows its lo-2) Coordinates estimation,

cation it can report the location of the detected event 3) Transformation from relative to absolute to the sink nodes. According to the embedded loca-coordinates.

tion information, the fire truck can then plan the route In comparison with the hop-count based ap-to the fire. Performance of target tracking, loca-proach [6], although the accuracy of DMS-MAP is tion-based routing, coverage management, and in-high, MDS-MAP still has the fol-lowing drawbacks:

formation dissemination protocols can be improved 1) The time complexity is high. When there are * Corresponding author. 197

第1页下一页