An improvement of DV-Hop localization algorithm for wireless sensor networks

With the high-speed development of the information industry today, Wireless sensor network (WSN) is produced and developed based on sensor technology, MEMS (Micro-Electro-Mechanism System) technology and wireless communications technology. It has been widely used in national defense, environmental monitoring, traffic management, health care, manufacturing, anti-terrorism and other disaster areas, and its low power consumption, low cost, distributed and self-Characteristics of the organization have brought a revolution in information perception.

Wireless sensor network is a new technology about acquiring and processing information, it can self-organize network topology structure. The nodes can monitor and collect various environmental or monitoring object information through collaborative work in real time, and process the information at the same time. In wireless sensor network, there is no location information is meaningless, so the node localization problem is one of the important common support technology in the wireless sensor networks and is highly regarded [1].

Localization algorithms for static wireless sensor networks are usually classified along several axes. A first distinction between localization algorithms deals with the use of anchor nodes. Network of nodes where no anchors are used usually establish their relative positions, possibly creating their own coordinate system. In general, the more anchors, the better the accuracy of the estimated locations. However, deploying anchors can be a tedious task and prove to be a rather expensive way of improving the accuracy of the localization algorithm. According to whether measures the actual distance between nodes in the positioning process, localization algorithm can be divided into: Range-based localization algorithm Range-free and localization algorithm.

Range-based localization algorithms use techniques such as radio signal strength indicator [2, 3] (RSSI) or radio and ultrasound with angle-of-arrival (AOA) or time-difference-of-arrival (TDOA), to measure the distance that separates an unlocalized node from an anchor. These distances, also called ranges, are sensitive to range errors, i.e., inaccuracies in the range measurements and often rely on additional hardware. To be independent of hardware and counter range inaccuracies, researchers developed range-free methods that depend uniquely on the information location, hop count-a node receives from its neighbors, be they anchors or regular nodes. And it includes centroid, convex programming, DV-Hop, Amorphous, MDS-MAP and APIT.

The Range-free needs low cost, and has high survival ability, positioning accuracy basically can satisfy the needs of practical application, so it has more practical value and development prospect, and it is one of the emphasis of research at the same time [4, 5].

DV-Hop algorithm was made by Dragons Niculescu from the Lutegesi University of United States etc., the basic idea is: the node itself only exchange information with its adjacent nodes, the distance between the unknown nodes and the anchor nodes is represented by the product of network average Hop distance and the shortest path between two nodes,and uses trilateral measurement to obtain the node location information [6, 7]. This algorithm requires some nodes have GPS positioning equipment, other nodes determines their own position according to anchor node (using GPS positioning or manual deployment of the nodes in advance, their exact location is known) and the communication information between the nodes. The nodes don’t need have distance measurement or Angle measurement function, also do not need additional location or Angle measuring equipment. So DV-Hop algorithm is one of the most widely applied algorithm in the large node self-localization algorithms for wireless sensor network.

DV-HOP algorithm can be divided into the following 3 steps [8, 9]:

Beacon nodes broadcast their location information packet to the neighbor, which included jumping section of the field, and the value is initialized to 0. Receiving node records the minimum hop count of each node, while ignoring the larger hop group from the same anchor node, then the jump number is added 1 and transmitted to neighbor nodes.

Each anchor node estimates the actual average hop distance using formula (1), according to the location information and the hop count of the other anchor nodes.

Among them: (x _i ,y _i ), (x _j ,y _j ) are the coordinates of the anchor node i,j; h _j  is the hop account between anchor node iand the anchor node j(i≠j).

Anchor nodes broadcast the average hop distance which use the grouping with a live field to the network. Unknown nodes, which only record the first received average hop distance and transmit the information to neighbor nodes. Then unknown nodes calculates the distance to every anchor node, according to the records of hop account.

The unknown nodes use trilateration or maximum likelihood estimation method to calculate the coordinates of the unknown nodes,according to the records of hop distance to each anchor node, using the trilateral value or maximum likelihood estimation method to calculate the unknown nodes of coordinates.

When the distances which are from all the anchor nodes to the unknown node P, we can use formula (2) to calculate: Meanwhile, formula (2) can be expressed as: Formula (3) means the linear equation for: Among them:

We can get the coordinates of the unknown node P through using the standard minimum mean variance estimation method to formula (5):

As shown in Fig. 1, the process of the improved algorithm can be as follows:

In order to test the performance of the improved algorithm, using MATLAB to simulate and analyze the traditional DV-HOP algorithm and the improved algorithm. As shown in Fig. 2, the nodes distribute in 100 m×100 m Square area, the unknown nodes and anchor nodes are randomly distributed in the area. Communication range of each node are set to 50 m. Below respectively discussing anchor node density, node density and thresholds M for the influence of the positioning error, each performance of the simulation were randomized 100 times.

This paper summarized the characteristics of the DV-Hop algorithm based on the analysis of DV-Hop algorithm, and presented an improved localization algorithm. Through theoretical analysis and experimental results, it can be seen that the improved algorithm significantly increases the positioning accuracy of the nodes compared with conventional DV-HOP algorithm, under the premise of maintaining simple, low cost. It is an effective scheme for the node localization in wireless sensor networks.