Linqing Gui
email: guilinqing@gmail.com

Thierry Val
email: val@irit.fr

Anne Wei
email: anne.wei@cnam.fr

Sami Taktak
email: sami.taktak@cnam.fr

An Adaptive Range-free Localisation Protocol in wireless sensor networks

Keywords: wireless sensor networks, localisation, range-free, algorithm, protocol

It is well known that localisation is a fundamental issue for many wireless network applications. Without the need of additional ranging devices, the range-free localisation technology is a cost-effective solution for low-cost indoor and outdoor wireless sensor networks. However, we noted that most existing algorithms were only studied using tools like MATLAB neglecting possible problems in a real wireless network context such as frame collision and node synchronisation. Thus, we propose an Adaptive Range-free Localisation Protocol (ALP) based on IEEE 802.15.4 standard, which can evaluate localisation algorithms. Using our localisation protocol, we investigate and compare the performance of our new approach to some existing range-free algorithms in terms of localisation accuracy, mobility, synchronisation and overhead. Our results show that our Mid-perpendicular, Checkout DV-hop and Selective 3-Anchor DV-hop algorithms support robust and dynamic localisation in the context of our adaptive localisation protocol.

Introduction

In recent years, wireless sensor networks have attracted worldwide research and industrial interest. They are typically composed of resource-constrained sensor nodes which can communicate with each other and cooperatively collect information from the environment. Wireless sensor networks can be deployed in various applications. For example, they can be used for parking space detection [START_REF] Vishnubhotla | ZigBee based multilevel parking vacancy monitoring system[END_REF], security surveillance [START_REF] Zhang | An indoor security system with a jumping robot as the surveillance terminal[END_REF], indoor object tracking (Lee and Chung, 2011) or monitoring services [START_REF] López | LOBIN: E-textile and wireless-sensor-network-based platform for healthcare monitoring in future hospital environments[END_REF][START_REF] Postolache | Smart sensors network for air quality monitoring applications[END_REF][START_REF] Tang | Channel characterization and link quality assessment of IEEE 802.15.4-compliant radio for factory environments[END_REF]. Note that it is important for sensor data to be combined with position information in many applications [START_REF] Vishnubhotla | ZigBee based multilevel parking vacancy monitoring system[END_REF]Lee and Chung, 2011;[START_REF] Gu | A survey of indoor positioning systems for wireless personal networks[END_REF][START_REF] López | LOBIN: E-textile and wireless-sensor-network-based platform for healthcare monitoring in future hospital environments[END_REF]. The position of sensors can also help to facilitate routing as well as determining the quality of coverage and achieving load balancing. Therefore, localisation has become a fundamental element in wireless sensor networks [START_REF] Vishnubhotla | ZigBee based multilevel parking vacancy monitoring system[END_REF][START_REF] Zhang | An indoor security system with a jumping robot as the surveillance terminal[END_REF]Lee and Chung, 2011;[START_REF] Gu | A survey of indoor positioning systems for wireless personal networks[END_REF][START_REF] López | LOBIN: E-textile and wireless-sensor-network-based platform for healthcare monitoring in future hospital environments[END_REF][START_REF] Postolache | Smart sensors network for air quality monitoring applications[END_REF][START_REF] Tang | Channel characterization and link quality assessment of IEEE 802.15.4-compliant radio for factory environments[END_REF][START_REF] Dai | Localisation algorithm for large-scale and low-density wireless sensor networks[END_REF][START_REF] Guerrero | A distributed range-free localization algorithm for wireless sensor networks based on a mobile robot[END_REF].

The existing localisation techniques can be generally categorised into two types: range-based and range-free. Range-based schemes [START_REF] Ouyang | GPS localization accuracy improvement by fusing terrestrial TOA measurements[END_REF]Kumar et al., 2009;[START_REF] Voltz | Maximum likelihood time of arrival estimation for real-time physical location tracking of 802.11a/g mobile stations in indoor environments[END_REF]Kovavisaruch and Ho, 2005;[START_REF] Rong | Angle of arrival localization for wireless sensor networks[END_REF] need first to precisely measure the range information (the distance or the angle) between concerned sensor nodes, and then to calculate the desired position based on trilateration or triangulation approaches. The ranging methods typically use Received Signal Strength Indicator (RSSI) (Kumar et al., 2009), Time of Arrival (TOA) [START_REF] Voltz | Maximum likelihood time of arrival estimation for real-time physical location tracking of 802.11a/g mobile stations in indoor environments[END_REF], Time Difference of Arrival (TDOA) (Kovavisaruch and Ho, 2005) and Angle of Arrival (AOA) [START_REF] Rong | Angle of arrival localization for wireless sensor networks[END_REF]. Global Positioning System (GPS) [START_REF] Ouyang | GPS localization accuracy improvement by fusing terrestrial TOA measurements[END_REF] is the most well-known range-based technique using TOA or TDOA. However, GPS devices not only consume lots of energy but also fail to work indoors. An alternative technique is GSM (Global System for Mobile communications), using RSSI and AOA methods. Note that GPS and GSM support localisation by using complex and expensive systems. Another technology is UWB (Ultra Wide Band) which can be used to measure time of flight with high precision [START_REF] Li | A 3-tier UWB-based indoor localization system for ultra-low-power sensor networks[END_REF]. The range-based techniques have two major drawbacks. First, the range information is very easily affected by multipath fading, noise and environmental variations. Second, additional ranging devices are usually needed which consume more energy and increase the overall cost.

While range-based scheme uses the distance or angle between nodes, the range-free scheme uses connectivity information between nodes. In this scheme, the nodes aware of their positions are called anchors, while other nodes are called normal nodes. Anchors are fixed, while normal nodes are usually mobile. Normal nodes first gather their connectivity information as well as positions of anchors. Then they calculate their own positions. Since no range information is needed, range-free scheme can be implemented on low-cost wireless sensor networks. Another advantage of range-free scheme is its robustness; connectivity information is not easily affected by the environment. As a result, we focus on the range-free scheme.

The typical range-free algorithms include Centroid [START_REF] Patro | Localization in wireless sensor network with mobile beacons[END_REF], CPE (Convex Position Estimation) [START_REF] Doherty | Convex position estimation in wireless sensor networks[END_REF], and DV-hop (Distance Vector-hop) [START_REF] Niculescu | DV based Positioning in ad hoc networks[END_REF]. Centroid and CPE have low complexity, but they require a normal node to have at least three neighbour anchors. The DV-hop algorithm can handle the case where a normal node has less than three neighbour anchors. It should be noted that, these localisation algorithms are not accurate enough. Then, in order to improve localisation accuracy, we have proposed several new algorithms such as Mid-perpendicular [START_REF] Gui | A two-level range-free localization algorithm for wireless sensor networks[END_REF], Checkout DV-hop [START_REF] Gui | A two-level range-free localization algorithm for wireless sensor networks[END_REF] and Selective 3-Anchor DV-hop [START_REF] Gui | Improving localization accuracy using selective 3-anchor DV-hop algorithm[END_REF].

However a common problem of range-free localisation algorithms has been neglected. That is, performances of these existing algorithms are studied by using tools like MATLAB which doesn't consider possible problems in a real wireless network context such as frame collisions and node synchronisation. Thus, we propose in this paper an ALP based on IEEE 802.15.4 standard, which can be used to evaluate localisation algorithms.

The main contributions of this paper are:

We propose ALP-3 protocol which is used to implement DV-hop based algorithms. In this novel protocol we design new data payload formats, and a new access method E-CSMA/CA to improve the performance of non-slotted CSMA/CA. In addition, several parameters such as timers and maximum number of received anchors are proposed to end each step of DV-hop based algorithms.

We also propose ALP+3 protocol to implement other algorithms such as Centroid, CPE and Mid-perpendicuar. In this protocol normal nodes broadcast their localisation request to neighbour nodes.

Then their neighbour anchors respond by sending back anchors' positions. Here, our E-CSMA/CA method is also used to reduce frame collisions.

We suggest an adaptive approach named as ALP protocol which combines ALP-3 protocol and ALP+3 protocol. The basic principle of this adaptive protocol is as follows: given the ratio of anchors, the network administrator can estimate the network overhead of both ALP-3 and ALP+3 protocols. Thus, the maximum acceptable network overhead has its corresponding maximum ratio of anchors which is defined as the threshold of ratio of anchors 'RA thres '. When the ratio of anchors is lower than RA thresh , ALP-3 protocol needs to be used; but when the ratio of anchors is higher than RA thresh , in order to avoid a large number of network traffic, ALP+3 protocol should be used.

Based on our protocols, using the network simulator WSNet, we simulate the concerned range-free localisation algorithms in the IEEE 802.15.4 wireless network. Comparative network simulation results are presented and analysed in terms of localisation accuracy, overhead, node mobility and node synchronisation.

The rest of this paper is organised as follows.

Section 2 introduces existing typical range-free localisation algorithms. Section 3 presents our improved algorithms such as Mid-perpendicular, Checkout DV-hop and Selective 3-Anchor DV-hop. In Section 4, our ALP is introduced. In Section 5, simulation results and analysis are given. Finally we give our conclusion and perspective in Section 6.

Related works

In this section we introduce and analyse the typical range-free localisation algorithms. Among them some algorithms that we mark as A+3 algorithms require a normal node to have at least three neighbour anchors. But others that we denote by A-3 algorithms do not have this constraint.

A+3 algorithms: Range-free algorithms with at least 3 neighbour anchors

When some range-free algorithms like Centroid and CPE localise a normal node, it is necessary for the normal node to have at least 3 anchors at range. Centroid algorithm was proposed by Bulusu [START_REF] Patro | Localization in wireless sensor network with mobile beacons[END_REF]. The basic principle is to look at the centroid point of neighbour anchors as the estimated position of the normal node. The author chooses a simple radio propagation model, which fits quite well for outdoor environment. In this model there are two assumptions: the first is perfect spherical radio propagation, and the second is identical transmission range for all radios.

Suppose that in the network there are m anchors situated at known positions A 1 (x 1 , y 1 ), A 2 (x 2 , y 2 ) … A m (x m , y m ). All these anchors have the same communication range denoted by R. Their transmission areas have an overlap. Inside the overlap locates the normal node N x . That means all these m anchors are the neighbour anchors of N x . Then N x localises itself at the centroid of these m anchors: The CPE (Convex Position Estimation) algorithm was proposed by Doherty [START_REF] Doherty | Convex position estimation in wireless sensor networks[END_REF]. The authors of CPE algorithm first provide an optimisation concept and then they propose to estimate positions of normal nodes using the results of a joint optimisation problem. The CPE algorithm is a centralised localisation scheme because the resource-limited normal node is unable to do numerous and complex calculations required by optimisation process. Thus, the original CPE algorithm scales poorly when the network is large. However, a simplified and distributed version of CPE algorithm has been proposed by some researchers [START_REF] Sheu | A distributed location estimating algorithm for wireless sensor networks[END_REF][START_REF] Sheu | A distributed localization scheme for wireless sensor networks with improved grid-scan and vector-based refinement[END_REF]. The simplified CPE algorithm defines an Estimated Rectangle (ER) which bounds the communication range of anchors, as shown in Figure 1 Centroid and the simplified CPE algorithms have both low network overhead and low calculation complexity. But their accuracy performance is not so good. It should be noted that the above algorithms work under the condition that a normal node has at least 3 neighbour anchors. However if the density of anchors is not very high in a network, some normal nodes may have less than 3 neighbour anchors.

In this case DV-hop based algorithms should be used.

A-3 algorithms: Range-free algorithms with less than 3 neighbour anchors

A-3 algorithms do not require a normal node to have at least 3 neighbour anchors. Here, they refer to DV-hop based algorithms. In this subsection we first introduce the original DV-hop algorithm and then some typical DV-hop based algorithms such as DDV-hop (Differential DV-hop), Self-adaptive DV-hop and Robust DV-hop.

DV-hop algorithm

The DV-hop algorithm was proposed by Niculescu [START_REF] Niculescu | DV based Positioning in ad hoc networks[END_REF]. It is a suitable solution for normal nodes having less than 3 neighbour anchors. As shown in Figure 2, although the normal node N x has only one neighbour anchor A 1 , N x can use DV-hop algorithm for localisation. It means that N x first gathers at least three anchors' positions via other normal nodes, then based on the hop counts and distances between N x and anchors, N x estimates its position. The algorithm consists of the following three steps. Step 1: each anchor A i broadcasts through the network a message containing the position of A i and a hop count field initialised as 0. This hop count value will increase with the number of hops during the broadcast of the message in the network. On the first reception of the message, every node N (either anchor or normal node) records the position of A i , and initialises hop i as the hop count value in the message.

Here, hop i is the minimum hop count between N and A i .

If the same message is received again, N updates hop i . If the received message contains a lower hop count value than hop i , N will update hop i with that lower hop count value, and relay the message. Otherwise, N will ignore the message. Through this mechanism, all the nodes in the network can get the minimum hop count to each anchor.

Step 2: when an anchor A i receives the positions of other anchors as well as the minimum hop counts to other anchors, A i can calculate its average distance per hop, denoted as dph i . Once dph i is calculated, it will be broadcasted by A i .

Step 3: when receiving dph i , the normal node N x multiplies hop i,Nx (its hop count to A i ) by dph i , so that Nx obtains its distance to each anchor A i , denoted as d i,Nx . Here, i {1, 2, …, m d }, if we assume that there are m d anchors.

Then each normal node N x can calculate its estimated position N DV-hop by trilateration. The detail of the calculations of N DV-hop can be found in [START_REF] Niculescu | DV based Positioning in ad hoc networks[END_REF].

Although DV-hop algorithm can localise normal nodes which have less than three neighbour anchors, its localisation accuracy needs to be improved (Hou et al., 2010;[START_REF] Zhang | DV-hop based self-adaptive positioning in wireless sensor networks[END_REF]Lee et al., 2010). Thus, many algorithms have been proposed in recent years. In the following, several typical algorithms will be analysed.

Typical DV-hop based algorithms

In this section we describe a few DV-hop based localisation algorithms such as DDV-hop (Differential DV-hop) (Hou et al., 2010), Self-adaptive DV-hop [START_REF] Zhang | DV-hop based self-adaptive positioning in wireless sensor networks[END_REF]Robust DV-hop (Lee et al., 2010).

DDV-hop: This algorithm modifies

Step 2 and Step 3 of the original DV-hop algorithm. In Step 2 of DDV-hop, each anchor A i not only broadcasts its distance-per-hop dph i through the network but also broadcasts the differential error of dph i to the entire network. The definition and calculation of this differential error can be found in Hou et al. (2010). In Step 3, DDV-hop and DV-hop differ on the calculation of the estimated distance between a normal node N x and each anchor A i . That is, N x uses its own distance-per-hop value denoted as dph Nx to replace the anchors' distance-per-hop dph i . Here, dph Nx is obtained as the weighted sum of all anchors' distance-per-hop. The weighting coefficients are decided by the differential error of anchors' distance-per-hop.

Self-Adaptive DV-hop: This algorithm is composed of two methods. Because the second method needs RSSI information, we only consider the first method of this self-adaptive algorithm. This algorithm has the same network overhead as the original DV-hop but slightly modifies Step 3. At Step 3, when a normal node N x calculates its estimated distance to A i , N x also uses its own distance-per-hop value denoted as dph adp to replace the anchors' distance-per-hop. dph adp is also obtained as the weighted sum of anchors' distance-per-hop. In this algorithm, when calculating dph adp , the weighting coefficient of dph i (each anchor A i 's distance-per-hop) is decided based on N x 's hop count to A i . The more hops between N x and A i , the smaller value assigned to the weighting coefficient of dph i .

Robust DV-hop: a Robust DV-hop (RDV-hop) algorithm is proposed in Lee et al. (2010). Different from the above two algorithms, in order to replace dph i (the average distance per hop of A i ), RDV-hop algorithm defines a distance-per-hop value between N x and A i , denoted by dph Nx,i . And dph Nx,i is calculated as the weighted sum of the distance-per-hop values between A i and every other anchor A k . Here the distance-per-hop between A i and A k is denoted as dph i,k . In the calculation of dph Nx,i , the weighing coefficient of dph i,k will have the maximum value, if N x is one node on the shortest path between A i and A k .

These typical DV-hop based algorithms use weighing methods to determine weighted distance-per-hop values for each normal node. However, in order to get a more accurate distance-per-hop value, sometimes additional information is demanded such as differential error in Hou et al. (2010) and hop counts between anchors in Lee et al. (2010). Broadcasting this additional information always increases the network traffic. We should also note that, the simulation results of the above algorithms are not so convincing because the distributions of sensor nodes are specifically designed rather than randomly obtained. For example, in [START_REF] Zhang | DV-hop based self-adaptive positioning in wireless sensor networks[END_REF] the anchors are distributed at the corners of the simulation area and the normal nodes are regularly distributed inside the area. Thus, in order to obtain a better accuracy without increasing the network overhead, we are motivated to provide improved methods which will be presented in the next section.

Improved range-free localisation algorithms

According to the previous analysis on the typical range-free algorithms, when a normal node has at least 3 neighbour anchors, it can localise itself using algorithms such as Centroid, CPE (in the paper from now on, it refers to simplified version of CPE). On the contrary, when a normal node has less than 3 neighbour anchors, the available localisation algorithms are only the DV-hop based algorithms.

This encourages us to categorise normal nodes into two types according to the number of neighbour anchors: the normal nodes having at least 3 neighbour anchors are noted as 'A+3' nodes, while others are 'A-3' nodes. For each type of normal nodes, we will present our improved localisation methods in the following.

Improved range-free algorithm for A+3 nodes

For A+3 normal nodes, Centroid and CPE are popular algorithms because of their low communication and computation cost, regardless of their inaccuracy. Our aim is to propose a new algorithm which can achieve a higher accuracy, at the cost of higher calculation complexity. The algorithm we have proposed is Mid-perpendicular [START_REF] Gui | A two-level range-free localization algorithm for wireless sensor networks[END_REF]. The basic principle of this algorithm is to find the centre of anchors communication overlap by perpendicular lines and consider this centre as the estimated position.

We first investigate the case when a normal node has only 3 neighbour anchors as shown in Figure 3(a). 'Line1' is the mid-perpendicular of the line connecting the anchors A 2 and A 3 . That means Line1 passes the middle point between A 2 and A 3 and crosses the line (which connects A 2 and A 3 ) at a right angle. According to the symmetry, Line1 goes through the centre of the overlap region. In the same manner, Line2 is the mid-perpendicular of the line connecting A 1 and A 3 , while Line3 is the mid-perpendicular of the line connecting A 1 and A 2 . Both Line2 and Line3 go through the centre of the overlap region. Thus, the cross point of the three mid-perpendiculars (Line1, Line2 and Line3) can be regarded as the centre of overlap. This cross point is denoted as N mid which is also the estimated position of Mid-perpendicular algorithm.

If the coordinates of the three anchors (A 1 , A 2 and A 3 ) are respectively (x 1 , y 1 ), (x 2 , y 2 ), and (x 3 , y 3 ), the cross point of the above two mid-perpendiculars denoted by N mid (x mid , y mid ) can then be calculated as: (2)

2 2 2 2 1 2 3 1 1 3 1 2 1 2 2 3 3 1 1 2 3 2 3 1 3 1 2 2 2 2 2 1 2 3 1 1 3 1 2 1 2 2 3 3 1 1 2 3 2 3 1 3 1 2 mid mid ( 2 2 ( )( ) ( )( ) ( )( )( ) [ ( ) ( ) ( )] )( ) ( )( ) ( )( )( ) [ ( ) ( ) ( )] x x x x x x x x x x x x x x x x x x x x x
It should be noted that there is one condition for the above derivation: N x 's 3 neighbour anchors (A 1 , A 2 and A 3 ) form an acute triangle where all the angles are less than 90 degrees. However, if the 3 neighbour anchors form a right triangle or an obtuse triangle, then the calculation of N mid will be much simpler: in this case, N mid is the middle point of the longest side in the triangle.

Then we investigate the case when a normal node has more than 3 neighbour anchors. Suppose that there are m neighbour anchors for the normal node N x , with m > 3. We have found that the overlap communication region of all the m anchors is contributed mainly by three anchors. In Figure 3 (b), the example has 4 neighbour anchors. From the figure, we can see that the overlap region formed by all the 4 anchors is actually the overlap of the three anchors A 1 , A 2 , and A 4 . These three anchors have the following characteristics:

Two of them have the longest distance compared with distances between any two of the entire anchors. That is because the two most distant anchors have the smallest overlap. In the example, the two most distant anchors are A 1 and A 4 .

The third anchor is farthest to the line connecting the two most distant anchors. In this example, since the two most distant anchors are A 1 and A 4 , the anchors except them are A 2 and A 3 . Compared with A 3 , A 2 has a longer distance to the line connecting A 1 and A 4 . Thus, the third anchor is A 2 . L. Gui et al.

Thus we know how to estimate the position of N x . First, N x calculates the distance between any two anchors. Since there are m neighbour anchors, there will be 2 m C distances in total. Comparing these distances, N x can find out the two farthest anchors, denoted by A i and A k . Then, among all other anchors except A i and A k , N x finds out the anchor which has the longest distance to the line connecting A i and A k . This anchor is denoted as A j . Thus, A i , A k and A j are the three anchors which contribute the overlap of all m anchors. Finally, using equation ( 2), N x calculates the centre of the overlap formed by A i , A k and A j , thus obtaining the final estimated position.

The simulation results in [START_REF] Gui | A two-level range-free localization algorithm for wireless sensor networks[END_REF] show that, with nodes randomly distributed, our Mid-perpendicular algorithm has a better localisation accuracy of about 15% than Centroid and CPE algorithms.

Improved range-free algorithms for A-3 nodes

In the previous section, we introduce our improved method to localise A+3 normal nodes. Now, we would like to focus on the case with A-3 normal nodes. Usually, in a network there are always a few anchors and much more normal nodes. As a result, most normal nodes will be A-3 nodes, having less than 3 neighbour anchors. DV-hop algorithm is frequently used to localise A-3 nodes. However, its accuracy should be improved. Thus, we have proposed Checkout DV-hop and Selective 3-Anchor DV-hop algorithms. In the following, we will introduce the principle of these two algorithms.

Checkout DV-hop algorithm

The key issue of DV-hop is calculating the approximate distance between the normal node N x and each anchor A i , by multiplying the hop count by the average distance per hop. This means:

, , = , 1, 2 i Nx i Nx i d dph hop i m (3)
where d i,Nx is the approximate distance between N x and A i , hop i,Nx is the minimal hop number between N x and A i , and dph i is the approximate average distance per hop of A i . Since d i,Nx is an important element for calculating the position of the normal node N x [START_REF] Niculescu | DV based Positioning in ad hoc networks[END_REF], it has a considerable influence on the accuracy of DV-hop. We denote the true distance from N x to A i by d i,NxTrue , and the difference between d i,NxTrue and d i,Nx by d i,Nx , where obviously d i,Nx is one reason for the inaccuracy of DV-hop. If we denote dph i by the difference between dhp i and its true value, then from equation (3) we have: In [START_REF] Gui | A two-level range-free localization algorithm for wireless sensor networks[END_REF], simulations have been done using MATLAB with the nodes randomly distributed in a square area. Results have proved that our Checkout DV-hop algorithm is about 15% more accurate than DV-hop algorithm.

Selective 3-anchor DV-hop algorithm

Although Checkout DV-hop algorithm is simple, its accuracy improvement is not so considerable. We observe that the accuracy can be improved if we find three anchors being at 'best' positions. Thus, we have proposed Selective 3-Anchor DV-hop algorithm. First, this algorithm generates a group of candidates. Then, from this pool, it chooses the best 3-Anchor group based on its connectivity vector.

Let us consider a network with m d anchors A 1 A 2 … A md . Through DV-hop algorithm, a normal node N x can obtain hop i,Nx , which is its minimum hop count to each anchor A i , as well as d i,Nx , which is the estimated distance between N x and A i . Then, N x can calculate its estimated position N DV-hop by trilateration based on the m d estimated distance values d 1,Nx d 2,Nx … d md,Nx . So, the quality of these estimated values has a great influence on the accuracy of DV-hop.

In fact, instead of using all m d estimated values, three estimated distance values to three different anchors are sufficient for N x to calculate its position. For example, we use d i,Nx , d j,Nx , d k,Nx , which are the three estimated distance values from N x to the three corresponding anchors A i , A j , A k . If we denote the true position of N x by (x, y), and the positions of A i A j A k respectively by (x i , y i ), (x j , y j ), (x k , y k ), then we can have the following equation:

2 2 2 , 2 2 2 , 2 2 2 , ( ) ( ) ( ) ( ) .

( ) ( )

i i i Nx j j j Nx k k k Nx x x
i j k i j k i j k i k i k j k j k i Nx k Nx i i k k j Nx k Nx j j k k N C B x x y y C x x y y d d x y x y B d d x y x y x y (7)
where the dimension of matrix C is 2 by 2 and that of matrix B is 2 by 1. Here, it should be mentioned that the three anchors A i A j A k cannot be collinear. Otherwise, matrix C will be singular. The principle of Selective 3-Anchor DV-hop algorithm is to select the most accurate 3-anchor estimated position and consider it as the final estimated position. Here the criterion for the selection is the connectivity of N x .

In DV-hop algorithm, the connectivity of N x is specified as the minimum hop counts between N x and anchors. For example, if there are m d anchors and the minimum hop count from N x to each anchor A i is hop i,Nx , then the connectivity of N x is the array [hop 1,Nx , hop 2,Nx ... hop md,Nx ]. In [START_REF] Gui | Improving localization accuracy using selective 3-anchor DV-hop algorithm[END_REF], we have given the relation between connectivity and distance: a smaller connectivity difference between two nodes will result in a smaller distance between them. According to this relationship, the 3-anchor estimated position which has the smallest connectivity difference to N x must be the nearest to N x . So, the basic principle of our Selective 3-Anchor DV-hop algorithm is to choose the 3-anchor estimated position which has the smallest connectivity difference to N x .

However, the connectivity of each 3-anchor estimated position N <i,j,k> is still unknown. We therefore give the following method to calculate the hop count between N <i,j,k> and each anchor.

Through the first two steps of DV-hop, N x can obtain anchors' positions as well as its minimum hop counts to all anchors. Then, based on equation ( 7), N x can get its 3-anchor estimated positions, each of them denoted by N <i,j,k> . So N x can calculate the distances between N <i,j,k> and each anchor A t , denoted by d <i,j,k>,t . Then the problem of calculating the hop count between N <i,j,k> and A t becomes the problem of calculating the distance per hop. Indeed, if N x knows the distance per hop between N <i,j,k> and A t , denoted by dph <i,j,k>,t , then N x can calculate the hop count between N <i,j,k> and A t according to equation (8) where hop <i,j,k>,t is the hop count between N <i,j,k> and A t : , , , , , , , , ,

i j k t i j k t i j k t d hop dph (8)
Then we must then find a method to estimate the value of dph <i,j,k>,t . In fact, all the distance-per-hop information that N x has obtained are anchors' distance-per-hop values: dph 1 , dph 2 , …, dph md , including the distance per hop of A t denoted as dph t . Thus, we need to estimate dph <i,j,k>,t based on the anchors' distance-per-hop values.

In order to get an approximate value of dph <i,j,k>,t , three kinds of position relation between N <i,j,k> and its nearest anchor A near are considered based on their distance. In the first case, the distance between N <i,j,k> and A near is so small that we can use the distance-per-hop value of A near (denoted by dph near ) as an approximate value of dph <i,j,k>,t. Here, as an example, we can set the distance threshold to half of the radio range of nodes. Of course, the best value of the threshold can be determined by simulations. The second case is the opposite: the distance between N <i,j,k> and A near is so large that we can only use dph t as an approximate value of dph <i,j,k>,t. Here, also as example, the threshold of distance is set to the radio range of nodes. Since the third case is between the above two cases, the value of dph <i,j,k>,t , in the third case can be set to the average of dph near and dph t . These three cases are shown in Figure 5. In this figure, N p and N q are two other normal nodes which connect N x and A t .

Summarising the three cases, we can estimate the value of dph <i,j,k>,t as follow: where d near is the distance between N <i,j,k> and A near , dph near is the distance per hop of A near . Using ( 8) and ( 9), N x can obtain hop <i,j,k>,t , which is the estimated hop count between N <i,j,k> and each anchor A t . Then, the connectivity difference between N <i,j,k> and N x can be calculated as The procedure of our Selective 3-Anchor DV-hop algorithm is summarised as follows. The first and second steps are the same as DV-hop algorithm. In the third step, a normal node N x selects any three non collinear anchors to form a 3-anchor group, and correspondingly generates a 3-anchor estimated position. Then, based on equations ( 8) and ( 9), N x calculates the connectivity of each 3-anchor estimated position. Finally, N x chooses the best 3-anchor estimated position which has the smallest connectivity difference to N x .

We should note an exceptional case concerning very low ratio of anchors. For example, in a network with 100 nodes with only five of them being anchors. In this case, some normal nodes may have the same connectivity, thus the algorithm will be quite inaccurate. In this case, checkout DV-hop algorithm is recommended.

simulation results by MATLAB in Gui et al. ( 2011) prove that, when the ratio of anchors is more than 10%, Selective 3-Anchor DV-hop algorithm achieves much better precision than other algorithms [START_REF] Niculescu | DV based Positioning in ad hoc networks[END_REF]Hou et al., 2010;[START_REF] Zhang | DV-hop based self-adaptive positioning in wireless sensor networks[END_REF]Lee et al., 2010;[START_REF] Gui | A two-level range-free localization algorithm for wireless sensor networks[END_REF]. The improvement of precision can be from 20% to 57% depending on the compared algorithms and the different scenarios.

ALP-3 protocol

Our ALP-3 protocol can be used to implement DV-hop based algorithms which localise the normal nodes with less than 3 neighbour anchors. In the following subsections, we will introduce ALP-3 protocol, including the formats of data payload, the improved collision reduction methods and the procedure of the protocol.

Proposed formats of data payload

Like DV-hop algorithm, ALP-3 protocol consists of 3 steps. At

Step 1, anchors need to broadcast their positions throughout the network. At Step 2, anchors also need to diffuse their distance-per-hop values. So we must define the frame formats for message exchange at the first two steps.

Conforming to the MAC general frame format specified in IEEE standard 802.15.4-2009, frames in ALP-3 protocol consist of three basic fields: MHR (MAC header), MAC payload and MFR (MAC footer), as shown in Table 1. We should mention that destination and source addresses use 16-bit short format. Since all frames in ALP-3 protocol are to be broadcasted, the destination address should be 0xffff. Two formats of data payload are proposed for the first two steps of ALP-3 protocol.

At Step 1, each anchor A i broadcasts through the network a position frame 'frame_pos i ' so that all nodes (including anchors and normal nodes) can know the position of A i and the minimum hop count to A i . The format of frame_pos i is shown in Table 2. In Table 2, the data payload is composed of four parts: 'Data Type', 'x i ' 'y i ' and 'HopCount'. Data Type identifies the type of information that the frame contains. In fact, in DV-hop algorithm, each anchor A i only needs to broadcasts two types of information: the position and the distance-per-hop. So we define that Data Type (1 bit) is '0' for a position frame, or '1' for a distance-per-hop frame. Here, it is '0' since 'frame_pos i ' is a position frame. 'HopCount' is the hop count value initialised to '0' by the initial sender A i . This hop count value will increase with augment of hop during the flooding of this frame. Here, HopCount is limited to 7 bits with a maximum value 127 that is sufficient for the network. 'x i ' and 'y i ' represents A i 's coordinates. 'x i ', as well as 'y i ', is a 32-bit single precision float-point value, conforming to the IEEE standard 754 (IEEE standard 754, 1985).

Then, at Step 2, A i broadcasts through the network a distance-per-hop frame 'frame_dph i ' which contains its average distance per hop dph i . Its format is shown in Table 3. The data payload of frame_dph i consists of Data Type and dph i . The value of Data Type is 1. 'dph i ' is a single precision float-point value. In our case the length of a single precision float-point value should be 32 bits. However, considering 'Data Type' is just 1 bit, we assume that the first bit of the float-point value is used for 'Data Type'. The other 31 bits are used for dph i . When a node retrieves the value of dph i , this node should automatically add one bit '0' to the end of dph i , so that a 32-bits float-point format can be obtained. Since '0' is the last bit, its influence on the value of dph i is very low. DV-hop based algorithms have not considered the problem of frame collisions which however is easy to happen during the broadcasts of frames at the first two steps of DV-hop algorithm. Even if the 802.15.4 non-slotted CSMA/CA is used as the MAC layer protocol, it cannot completely solve the collision problem. That is because usually, in point-to-point communication, the CSMA/CA scheme generates the ACK (acknowledgement) signal to ensure a final successful transmission. However, in DV-hop algorithm, since all the communications are fulfilled as broadcast, no ACK signal is sent, so it becomes non-slotted CSMA/CA without ACK, which cannot make sure transmissions succeed. So we must propose a solution to effectively reduce collisions. In the following we first analyse how the collisions take place and then introduce our solution E-CSMA/CA (non-slotted Enhanced CSMA/CA without ACK).

Collisions may happen when anchors simultaneously broadcast their position frames or distance-per-hop frames. According to the principle of CSMA/CA without ACK, each anchor needs first to wait for a short random period and then, if the channel is still free, sends the frame immediately. Here, the short random period is randomly chosen among 8 values: 0, t bo , 2 × t bo , …, 7 × t bo (IEEE Standard 802.15.4-2009, 2009), where t bo is the back-off period. According to the IEEE standard 802.15.4-2009, if the data rate is 250 kbps, then t bo is 320 µs and the maximum value of this random period is 7 × 320 µs = 2.24 ms. With such a short random waiting period, when frames are simultaneously broadcasted throughout the network, collisions easily occur.

L. Gui et al.

The solution we use to reduce collisions is to make the senders (nodes ready for sending frames) wait for another longer random duration before they perform CSMA/CA. So the probability of collision can be reduced. Details about this longer waiting period are described in the following.

At the beginning of Step 1 of DV-hop, each anchor A i first waits for a random duration denoted by t wpi . Then, A i performs CSMA/CA and sends its position frame. Similarly, at the beginning of Step 2 of DV-hop, after each anchor A i has calculated its distance per hop denoted by dph i , it waits for a random duration denoted by t wdi . Then, A i performs CSMA/CA before sending its distance-per-hop frame frame_dph i .

Figure 6 shows how collisions happen while Figure 7 shows how our access method E-CSMA/CA works.

In Figure 6, three anchors A 1 A 2 A 3 start their first step simultaneously at the time T 0 . Then, they perform the non-slotted CSMA/CA without ACK. A 1 and A 2 happen to choose the same period 2×t bo . Since A 1 and A 2 send out their position frames at the same time, the two frames will arrive simultaneously at the common neighbour node of both A 1 and A 2 . Thus a collision occurs. The same phenomenon could happen at Step 2 with A 2 and A 3 choosing the same waiting period 1×t bo . Figure 7 shows an example of our collision reduction method using the same scenario of Figure 6. Comparing these two figures, we can see that our method adds an extra random duration before the beginning of the CSMA/CA procedure at each anchor. At the cost of additional waiting time, our method reduces the probability of simultaneous emissions; therefore, fewer collisions can occur. In fact, our collision reduction method E-CSMA/CA should also be applied to the relay nodes. These relay nodes, either anchors or normal nodes, help relay the position frame or distance-per-hop frame by broadcast. According to our method, every time a relay node is ready to perform CSMA/CA, this node needs to wait for an additional random duration t wr .

Through simulations we have observed that collision probability can be effectively reduced by our E-CSMA/CA method. In the simulations, a small network is located in a 40 × 40 m 2 area. Inside the area, we uniform-randomly distribute 10 nodes. That means, the positions of the nodes are randomly assigned. All the nodes are static. The topology of reference network is shown in Figure 8. Ideally, all nodes can receive and then relay the position frame from each anchor. However, in Figure 9(a), we can observe that, using non-slotted CSMA/CA when the anchors broadcast their positions simultaneously, nobody receives the position of A 2 while the position frame of A 3 is only received by N 6 . Why other nodes cannot receive the position of A 2 or A 3 ? The reason should be frame collisions. For example, from the network topology in Figure 8, since A 3 has only one neighbour node N 6 , its position frame should be first received by N 6 . Then, N 6 relays the position frame of A 3 . The neighbour of N 6 , that is N 7 , is supposed to receive this relayed frame. But at the same time, N 7 is also relaying the position frame of A 0 . Thus, collision happens on these two relayed frames.

On contrary, good results are shown in Figure 9(b) for our E-CSMA/CA method. We can notice that the position frame from each anchor has been successfully received and relayed by all nodes which shows that no collisions exist. This is contributed by the random waiting time added to non-slotted CSMA/CA.

A similar phenomenon can also be observed for Step 2. Considering the similarity of simulation results for Step 1 and Step 2, here we do not give the result figure of Step 2. From the simulation results, we can conclude that our E-CSMA/CA method is an efficient solution to reduce the frame collisions in DV-hop localisation algorithm.

Parameters for the end of each step

In DV-hop algorithm, Step 1 ends as soon as every node in the network has received all anchors' position frames while

Step 2 ends on condition that all anchors' distance-per-hop frames have been received. These ending conditions can be fulfilled in an ideal scenario by a mathematic simulator such as MATLAB. However, in practical network scenarios, the ending conditions cannot be reached because of two issues.

In the following, we analyse the issues and propose several parameters to control the end of the first two steps of DV-hop.

As for the first issue, it is unnecessary for nodes to receive all anchors' positions, especially when the number of anchors is very large, because mobile normal nodes need to calculate their positions as quickly as possible. Therefore, each node needs to set a maximum number of anchors whose information they take into account. This maximum number can be denoted by 'num_wait_pos'. As long as a normal node has received num_wait_pos anchors' positions, it can stop relaying position frames and end Step 1. As for anchors, when an anchor has received num_wait_pos-1 anchors' positions, it can end Step 1. (Here, it's 'num_wait_pos-1', because the number 'num_wait_pos' includes A i ). Similarly, if a normal node has received num_wait_dph anchors' distance-per-hop, it can end Step 2. Normally, num_wait_pos is no less than num_wait_dph.

The second issue occurs when collisions happen or the total number of anchors is less than 'num_wait_pos' or 'num_wait_dph'. When collisions exist at the first two steps of DV-hop algorithm, a few nodes may miss some anchors' position frames as well as distance-per-hop frames. As a result, these nodes may never receive as many as 'num_wait_pos' anchors positions, neither num_wait_dph anchors' distance-per-hop. Of course, this phenomenon could also happen if the total number of anchors is less than 'num_wait_pos' or 'num_wait_dph'. Timers will be used to solve this issue.

In order to end Step 1, we need to set a timer for each node N i at the time instant 0 1 . In DV-hop algorithm, all broadcasts of frames are included at Step 1 and 2, while Step 3 only includes position calculation. Since broadcasts usually take much more time than calculation, the total duration of Step 1 and Step 2 is very close to the entire period of localisation t p . That is, t s1 + t s2 t p . Besides, since Step 1 and Step 2 both broadcast frames, their duration should be similar. We can consider t s1 t s2 . For example, t s1 could be set as t p /2, while t s2 could be set as t p (3/8). Then, the time left is devoted to Step 3, that is: t pt s1t s2 = t p /8.

Procedure of ALP-3 protocol

The execution of ALP-3 protocol is shown in the following figure. Figure 10(a) shows the procedure followed by each anchor A i . The period begins at T 0 i . Then, according to our collision avoidance method E-CSMA/CA, A i first waits for a random duration t wpi , and then broadcasts through the network its position frame which has been defined in Section 4.1.1. Meanwhile, A i also receives and relays the positions frames of other anchors. When A i has received 'num_wait_pos-1' anchors' position frames, it will immediately end Step 1 and enter Step 2. This time instant is denoted as Tr i . However, if A i couldn't receive as many as 'num_wait_pos-1' anchors' position frames until the time instant 0 1 , i s T t it will still end Step 1 at 0 1 .

i s T t After Step 1, A i begins Step 2 by calculating its distance-per-hop. Then, A i waits for a random duration t wdi and broadcasts through the network its distance-per-hop frame. Meanwhile, A i also helps relay the distance-per-hop frames of other anchors. Here, the end of A i 's Step 2 is also the end of its participation in the localisation period since the third step is designed for normal nodes.

Figure 10(b) shows the procedure for each normal node N j . It begins its period at 0 . j T During the first two steps, N j receives and relays anchors' frames. When N j has received as many as num_wait_pos anchors' positions and as many as num_wait_dph anchors' distance-per-hop, it will immediately end the first two steps and start the third step. This time instant is denoted as Tr j . However, if N j could not receive as many as num_wait_dph distance-perhop frames until the time 0 1 2 , j s s T t t it will end Step 2 anyway.

ALP+3 protocol

In the previous section, we focused on ALP-3 protocol which is very useful to localise A-3 normal nodes (with less than 3 neighbour anchors). However, we should note a disadvantage of DV-hop based algorithms implemented by ALP-3 protocol: the high network overhead when there are many anchors. In fact, when the ratio of anchors is high, normal nodes can have at least 3 neighbour anchors. In this case, instead of using DV-hop based algorithms, we recommend the A+3 algorithms, such as Centroid, CPE and Mid-perpendicuar. Therefore, we propose ALP+3 protocol which can implement those A+3 algorithms. ALP+3 protocol is supposed to function in case of high ratio of anchors. In this case, we do not suggest that all anchors periodically broadcast their positions, because this leads to much more network overhead. It is better for the anchors to broadcast positions only when normal nodes ask them to do it. Thus, the basic principle of ALP+3 protocol is as follows, including 3 steps. First, when a normal node N x needs to calculate its position, it broadcasts a localisation request to its neighbourhood. Second, if a neighbour anchor of N x detects this request, this anchor sends its position to N x . Finally, if the node has collected at least 3 neighbour anchors' positions during a certain period, N x can calculate its position by Centroid, CPE or Midperpendicular.

In the following, the protocol is explained in details. At Step 1, the normal node N x broadcasts to its neighbourhood a localisation request frame, denoted as frame_req. When broadcasting frame_req, our E-CSMA/CA method should be used to reduce collisions because several normal nodes may be simultaneously ready to send their request frames. Here, the additional random waiting time in E-CSMA/CA method is denoted as t wlr . Considering this request frame is broadcasted, no ACK signal is required.

frame_req conforms to the command frame format in IEEE standard 802.15.4-2009. Shown in Table 4, frame_req has 3 parts: MHR, MAC payload and MFR. Since frame_req is broadcasted by N x , the source address must be the address of N x . The MAC payload only has an 8-bit field 'Command Type'. Its value is set to be 04.

According to the IEEE standard, this value means frame_req is used to request data (positions of anchors).

At

Step 2, the anchors who have received N x 's frame_req should send their positions to N x . These anchors are N x 's neighbour anchors. The number of neighbour anchors is at least 3, maybe even bigger such as 7 or 8, depending on the specific scenario. If all these neighbour anchors demand each normal node N x to send back ACK signals, then the network overhead will increase a lot. So, at this step, no ACK signal is demanded.

The position frame sent by the anchor A i to N x is denoted as frame_pos i,Nx . It conforms to the data frame format in IEEE standard 802.15.4-2009. Shown in Table 5, the source address is the 16-bit short MAC address of A i , while the destination address is that of N x . Data payload comprises the coordinate of A i .

For transmitting frame_pos i,Nx , our E-CSMA/CA method is recommended to reduce frame collisions. Because N x may have quite a few neighbour anchors (for example, as many as 6), all these anchors receive N x 's localisation request at the same time. If they perform non-slotted CSMA/CA before sending position frames, since the random waiting time is very small, two anchors may simultaneously send out frames, resulting in a collision. Thus, we can use E-CSMA/CA method which has an additional random waiting time, denoted by t wpi .

Before Step 3, assume that N x has received m anchors' position frames during a period t recv . Here, t recv is also the duration of Step 1 and 2 because N x is always collecting anchors' positions after sending the request. At Step 3, L. Gui et al. N x calculates its position. An example of the procedure for ALP+3 protocol is shown in Figure 11.

Adaptive Range-free Localisation Protocol (ALP): Combination of ALP-3 and ALP+3

ALP-3 protocol and ALP+3 protocol both have advantages and disadvantages. ALP+3 protocol is simple but it requires normal node has at least 3 neighbour anchors. ALP-3 protocol can serve the case of low ratio of anchors but it has considerable network overhead. In order to take advantage of the two protocols, the combination of the above two protocols is regarded as our ALP.

In this adaptive protocol, the choice between ALP-3 protocol and ALP+3 protocol can be decided by each normal node or by network administrator. If it is decided by each normal node, the corresponding protocol is chosen according to the number of neighbour anchors. That means, a normal node will choose ALP+3 protocol when it has at least 3 neighbour anchors; otherwise, it will choose ALP-3 protocol. But this method has a practical problem considering the different communication manners between the two protocols. In ALP+3 protocol, anchors are in passive mode: they wait for requests from normal nodes, if receive a request, they broadcast position frames only to neighbours. However, in ALP-3 protocol, anchors are in active mode: they do not need to listen to request, and they should broadcast their positions related information throughout the network. Suppose that in a network, anchors stay in passive mode by default, and most normal nodes use ALP+3 protocol, while only one normal node needs to use ALP-3 protocol. The problem is how the particular one normal node informs all anchors to change from passive mode into active mode. The solution can be: this normal node broadcasts a special request frame throughout the network; when receiving this special frame, anchors need to begin the process of ALP-3 protocol. We can notice that the broadcast of this special frame increases the network overhead.

Thus, we suggest that the choice between the two protocols is decided by the network administrator. So, when the choice is made, the network will use one protocol, ALP+3 or ALP-3. In fact, in case of high ratio of anchors, considering the network overhead, ALP+3 protocol is a better solution than ALP-3 protocol. Thus, in order to choose the proper protocol, we need to set a threshold for the ratio of anchors, denoted by RA thresh .

Suppose that in the network the number of anchors is stable and the administrator has known the ratio of anchors. Then, if the ratio of anchors is lower than RA thresh , the administrator chooses ALP-3 protocol because normal nodes are mostly A-3 nodes. But when the ratio of anchors is higher than RA thresh , in order to avoid a large number of network traffic, ALP+3 protocol should be used.

The value of RA thresh is decided by the administrator according to the maximum traffic that the network can accept. A lower RA thresh indicates the network can only accept lower network overhead. But the value of RA thresh cannot be too low; otherwise, many A-3 normal nodes are unable to be localised. After the administrator sets the value for RA thresh , comparing the ratio of anchors with RA thresh , the corresponding protocol can be chosen. The idea is summarised in Figure 12.

Simulation scenarios

The simulator we use is WSNet which is an event-driven simulator designed by three researchers from INRIA (http://wsnet.gforge.inria.fr/tutorial.html). Compared to others like NS-2 and OPNET, WSNet not only facilitates the development of new models, but also supplies sufficient modules at each layer (Hamida et al., 2008). Using WSNet, we have implemented our ALP protocol as a model in C language. The simulation scenarios take place within a 100 × 100 m 2 area. Inside the area, 100 nodes including anchors and normal nodes are randomly distributed. Scenario parameters and their values are listed in Table 6.

As shown in the table, RA thresh is set to be 40%. That means, when the ratio of anchors is less than 40%, ALP-3 protocol is used. When the ratio of anchors is no less than 40%, ALP+3 protocol turns to work.

Simulation results and related analysis

The simulation results of three scenarios (static, synchronised mobile, and unsynchronised mobile) are presented in Figure 13 and 14. The data is collected at each ratio of anchors. Figure 13 shows the average location error per node per localisation period, expressed as a percentage of the radio range. Figure 14 presents the average number of transmitted frames per localisation period. In total, six algorithms are compared. Three of them are DV-hop based algorithms, including DV-hop, Checkout DV-hop and Selective 3-Anchor DV-hop which are evaluated based on ALP-3 protocol. The others are A+3 algorithms, such as Centroid, CPE and Mid-perpendicular which function with ALP+3 protocol.

The average location errors of the algorithms in static scenario are shown in Figure 13(a). We can notice that all the A+3 algorithms have much better accuracy than DV-hop and Checkout DV-hop while the ratio of anchors is no less than 40%. We can also notice that, among the three A+3 algorithms, our Mid-perpendicular algorithm has the best accuracy, although the improvement is only about 15% on average.

Figure 13(b) shows the average location error of algorithms in synchronised mobile scenario. Comparing Figure 13(a) and Figure 13(b), we can note that, when nodes change from static to mobile, the accuracy of A+3 algorithms decreases a little. However, the accuracy of DV-hop based algorithms has a larger decrease.

This small decrease of A+3 algorithms is contributed by the small localisation period of ALP+3 protocol which is only 3 s. Considering the speed of nodes movement is 0.5 m/s, normal nodes move only 0.5 × 3 = 1.5 m. However, in ALP-3 protocol for DV-hop based algorithms, frames need to have enough time to broadcast through the network, thus the localisation period of ALP-3 protocol is configured as long as 6 s. During 6 seconds, normal nodes can move as L. Gui et al. far as 0.5 × 6 = 3 m. Therefore, node movement has a more important influence on the accuracy of ALP-3 protocol than that of ALP+3 protocol.

Figure 13(c) presents the average location error in unsynchronised mobile scenario. Comparing Figure 13(b) with Figure 13(c), we can see the different improvement of ALP-3 protocol and ALP+3 protocol. Based on ALP-3 protocol, DV-hop based algorithms have an obvious accuracy improvement in unsynchronised mobile scenario compared with the accuracy in synchronised mobile scenario. However, A+3 algorithms only have a slight improvement in unsynchronised mobile scenario. The reason is as follows. ALP-3 protocol has a large number of broadcast traffic, while ALP+3 protocol has much lower traffic. So, the possibility of frame collisions in ALP+3 protocol is much lower than that in ALP-3 protocol. Thus, as for ALP+3 protocol, the few collisions can be effectively reduced by our E-CSMA/CA method resulting in no significant change between synchronised scenario and unsynchronised scenario. However, considering the massive traffic in ALP-3 protocol, our E-CSMA/CA may be not enough to avoid collisions. In unsynchronised scenario, nodes (especially the anchors) begin their broadcast periods at different time, so it helps to further reduce frame collisions. Therefore, as for ALP-3 protocol, the accuracy in unsynchronised scenario is obviously better than in synchronised scenario.

In the following, the network overhead is investigated. All DV-hop based algorithms use the same protocol: our ALP-3 protocol. Thus they have the same network overhead. The A+3 algorithms using our ALP+3 protocol also have the same network overhead. Therefore, we need to compare the network overhead of ALP-3 protocol with that of ALP+3 protocol.

The network overhead of the protocols is quantised by the average number of transmitted frames by all 100 nodes per localisation period. Simulation results are shown in Figure 12. From this figure, we can notice that the network overhead of ALP-3 protocol is much higher than that of ALP+3 protocol. Now, we estimate the approximate value of number of transmitted frames for ALP-3 and ALP+3 protocols. In ALP-3 protocol, the network traffics exist only at the first two steps. At Step 1, each anchor A i broadcasts its position frame frame_pos i throughout the network. In order to make all nodes be aware of frame_pos i , every node in the network needs to relay this frame once. Thus, if the total number of nodes is num, the number of anchors is num × 'ratio of anchors', so the number of transmitted frames at Step 1 of ALP-3 protocol is at least num × (num × 'ratio of anchors') = num 2 × 'ratio of anchors'. The same result can be obtained for Step 2. Thus, as for all the three scenarios, the approximate value of number of transmitted frames for ALP-3 protocol is 2 num 2 × 'ratio of anchors'. To verify this, for example in Figure 12, when the ratio of anchors is 5%, the number of transmitted frames is about 1000. This value is just 2 × 100 2 × 5% considering the total number of nodes is 100. In ALP+3 protocol, the network overhead also exists only at the first two steps. At Step 1, each normal node broadcasts its localisation request just to its neighbour nodes. Thus, the number of transmitted frames at Step 1 is exactly num × (1 -'ratio of anchors') which is also the number of normal nodes. At Step 2, the neighbour anchors of each normal node respond the request by sending back their positions. Thus, if on average there are m neighbour anchors for each normal node, then the approximate value of number of transmitted frames for ALP+3 protocol is num × (1 -'ratio of anchors') m. To verify this result, for example in Figure 12, when the ratio of anchors is 40%, the number of transmitted frames is about 250 which is nearly 100 × (1 -40%) × 4 = 240, where m is assumed to be 4. Considering m is usually a small value (at least 3) depending on network topology and the ratio of anchors, the number of transmitted frames of ALP+3 protocol is much less than that of ALP-3 protocol.

L. Gui et al. network scenarios, some problems such as frame collisions, node mobility and synchronisation, should be taken into consideration. Thus, based on IEEE standard 802.15.4-2009, we propose in this paper an ALP which is a combination of ALP-3 protocol and ALP+3 protocol.

Table 7

Brief comparison on the protocols and algorithms In our ALP-3 protocol, we design new data payload formats and a new access method E-CSMA/CA to improve the performance of non-slotted CSMA/CA. In addition, several parameters such as timers and maximum number of received anchors are proposed to end each step of DV-hop based algorithms. ALP-3protocol can be used to implement the DV-hop based algorithms, including the original DVhop algorithm, our Checkout DV-hop algorithm and our Selective 3-Anchor DV-hop algorithm.

In our ALP+3 protocol, normal nodes broadcast their localisation request to neighbour nodes and then their neighbour anchors respond by sending back anchors' positions. In the protocol, we design new data payload formats and our E-CSMA/CA method is also used to reduce frame collisions. ALP+3 protocol can be used to implement the A+3 algorithms including Centroid, CPE and Midperpendicular.

Our protocols are implemented using the simulator WSNet in the IEEE 802.15.4 wireless network. Comparative network simulation results are presented and analysed in terms of localisation accuracy, overhead, node mobility and node synchronisation. Results show that, globally, our new algorithms have better accuracy than the existing typical range-free algorithms. We can also note that, in term of overhead, DV-hop based algorithms have much higher network overhead than A+3 algorithms like Centroid and CPE because DV-hop based algorithms require to broadcast throughout the network. In terms of mobility, node mobility can have a more important influence on the accuracy of DV-hop based algorithms than that of A+3 algorithms. Finally, it should be noted that node synchronisation is not necessary for our protocols in ad hoc topology.

In the future, we will make our ALP protocol work automatically without the configuration of network administrator. In this paper, the network administrator chooses ALP-3 or ALP+3 protocol for all nodes. This mechanism has low network overhead. But it is not flexible because the network can change with node movement, node failure and new association. Thus, we will investigate a new mechanism to let each node choose its proper protocol without much increase of network overhead.

Figure 2

 2 Figure 2 Example of topology in DV-hop algorithm (see online version for colours)

Figure 3

 3 Figure 3 Mid-perpendicular in different cases: (a) case with 3 neighbour anchors (b) case with more than 3 neighbour anchors (see online version for colours)

  indicates that when hop i,Nx increases, d i,Nx also increases, and the accuracy of DV-hop decreases. If A near is the nearest anchor to N x among all anchors A 1 A 2 … A m , then correspondingly hop near,Nx is the smallest, so that d near,Nx is the smallest position error. So we can conclude that, compared to other anchors, the distance from the normal node N x to its nearest anchor A near , denoted by d near,Nx , has the highest reliability in terms of precision. Checkout DV-hop algorithm will make best use of this concept to improve the accuracy using the most reliable information available.Now we illustrate the principle of Checkout DV-hop algorithm. It adds a checkout step to DV-hop algorithm, as shown in Figure4. For the purpose of comparison, Figure4(a) shows the result of DV-hop without 'checkout', while Figure4(b) shows the impact of our checkout step. As shown in Figure4(a), the normal node N x uses DV-hop to obtain its estimated position at N DV-hop with its coordinates denoted by (x , y ). Then it calculates the distance between N DV-hop and A near (here, A near is A 1 ), denoted by d DV-hop . Note that N x has used equation (3) to evaluate its approximate distance to the nearest anchor A near , denoted by d near,Nx.

Figure 4

 4 Figure 4 Principle of checkout DV-hop: (a) DV-hop and (b) checkout DV-hop (see online version for colours)

  anchor estimated positions, N x selects the position having the smallest connectivity difference as the final estimated position.

Figure 5

 5 Figure 5 Three kinds of relative positions: (a) d near < range/2; (b) d near > range and (c) range/2 < d near < range (see online version for colours)

Figure 6 Figure 7

 67 Figure 6 Collisions occur at Step 1 and Step 2 (see online version for colours)

Figure 8

 8 Figure 8 Network topology in the simulation (see online version for colours)

Figure 9

 9 Figure 9 Step 1 of DV-hop algorithm simulated by WSNet: (a) non-slotted CSMA/CA and (b) our E-CSMA/CA

Figure 10

 10 Figure 10 Procedure of ALP-3 protocol: (a) procedure for each anchor A i and (b) procedure for each normal node N j

Figure 11

 11 Figure 11 Example of procedure of ALP+3 protocol: (a) network topology and (b) procedure of ALP+3 protocol (see online version for colours)

Figure 12

 12 Figure 12 Basic principle of Adaptive Range-free Localisation Protocol (ALP)

Figure 13 Figure 14

 1314 Figure 13 Location error in different scenarios with ALP protocol: (a) location error in static scenario; (b) location error in synchronised mobile scenario and (c) location error in unsynchronised mobile scenario (see online version for colours)

  . Its centre point, denoted by N ER , is the estimated position of the simplified CPE algorithm, calculated as:

	x	ER	min i	i x	2	max i	i x	,	y	ER	min i	i y	2	max i	i y	.

Figure 1 Example of a simplified CPE algorithm (see online version for colours)

Table 2

 2 Format of frame_pos i

		Data Payload
	MHR	Data Type (1 bit) (in total 8 bits) HopCount (7 bits)	xi (32 bits)	yi (32 bits)	MFR

Table 3

 3 Format of frame_dhp i

		Data Payload
	MHR	Data Type (1 bit)	dphi (31 bits)	MFR
		in total 32 bits
	4.1.2 Proposed enhanced CSMA/CA (E-CSMA/CA)
		access method
	The IEEE standard 802.15.4-2009 defines several channel
	access methods that can help to reduce collisions,
	for example slotted CSMA/CA and non-slotted CSMA/CA.
	The slotted CSMA/CA method requires a network
	coordinator to frequently send messages for synchronisation
	and network association. However non-slotted CSMA/CA
	does not require these transmissions. So it can be used
	not only with star or tree networks, but also with

ad-hoc networks. Due to this simplicity and flexibility, non-slotted CSMA/CA is a popular method for low-cost sensor networks. Thus, in this paper, we mainly focus on non-slotted CSMA/CA method.

Table 4

 4 Format of frame_req

			MHR		MAC Payload	MFR
	Frame Control (16 bits)	Sequence Number (8 bits)	Destination Address (0xffff, 16 bits)	Source Address (16 bits)	Command Type (0x04, 8 bits)	FCS (16 bits)

Table 5

 5 Format of frame_ pos i,Nx

		MHR		Data Payload MFR
	Frame Control (16 bits)	Sequence Number (8 bits)	Destination Address (16 bits)	Source Address (16 bits)	xi (32 its)	yi (32 bits)	FCS (16 bits)

Table 6

 6 Scenario parameters (continued)

	Maximum number:	30
	num_wait_pos (ALP-3 protocol)
	Maximum number:	20
	num_wait_dph (ALP-3 protocol)
	RA thresh (ALP+3 protocol)	40%
	Normal node's waiting time:	Randomly selected between
	t wlr (ALP+3 protocol)	0 and 100 ms
	A i 's waiting time:	Randomly selected between 0
	t wpi (ALP+3 protocol)	and 100 ms
	t recv (duration of Step 1 and 2)	2.5 s
	(ALP+3 protocol)
	Network synchronised or not	Synchronised (all nodes start at
		the same time)
		Unsynchronised
	Nodes mobility	Static (for all nodes)
		Mobile (anchors static, but
		normal nodes move at a speed
		of 0.5 m/s in billiard mode)

Brief summary of evaluations on ALP protocol

From the above analysis on simulation results, we have noted that: ALP-3 protocol has much higher overhead than ALP+3 protocol. The overhead can be quantised by the metric 'number of transmitted frames'. The approximate value of number of transmitted frames for ALP-3 protocol is 2 num 2 × "ratio of anchors" while that for ALP+3 protocol is num × (1 -"ratio of anchors") m, where m is the average number of neighbour anchors for each normal node and num is the total number of nodes. So, given the ratio of anchors, the network administrator can estimate the network overhead for both protocols.

Thus, the maximum acceptable network overhead has its corresponding maximum ratio of anchors which is defined as the threshold of ratio of anchors 'RA thres '. When the ratio of anchors is lower than RA thresh , ALP-3 protocol needs to be used; but when the ratio of anchors is higher than RA thresh , in order to avoid a large number of network traffic, ALP+3 protocol should be used. This is also the basic principle of our ALP protocol.

Based on the corresponding protocols, the accuracy of the related algorithms has been evaluated in network scenarios. Although the improvement by our Mid-perpendicular algorithm and Checkout DV-hop algorithm is not so significant, our Selective 3-Anchor DV-hop algorithm has an accuracy about 35% better than our Checkout DV-hop algorithm and about 50% better than DV-hop algorithm.

Node mobility has a bigger influence on the accuracy of DV-hop based algorithms than that of A+3 algorithms. The reason is: while ALP+3 protocol has the broadcast only to neighbour nodes, ALP-3 protocol need more time to broadcast information throughout the network. Thus, the localisation period of ALP-3 protocol is longer than that of ALP+3 protocol. Therefore, moving at the same speed in ALP-3 protocol, normal nodes move away further during one period than in ALP+3 protocol.

Synchronisation also has an important influence on ALP-3 protocol. Compared with synchronised mobile scenario, ALP-3 protocol has an obvious accuracy improvement in unsynchronised mobile scenario. However, ALP+3 protocol only has a slight improvement in unsynchronised scenario. This reveals that our E-CSMA/CA method is already qualified for ALP+3 protocol but not sufficient for ALP-3 protocol. After all, synchronisation is not a necessary condition for both protocols.

As for calculation time, for both protocols, since the position calculation is restricted to Step 3, the calculation time does not exceed the duration of Step 3. In our simulation, the duration of Step 3 for ALP-3 protocol is set to be 0.75 s while that for ALP+3 protocol is 0.5 s. Therefore, all the related algorithms spend a little time calculating the position.

Table 7 gives a brief comparison on accuracy and overhead of the protocols.

Conclusions and perspectives

In the context of low-cost wireless ad-hoc sensor networks, the range-free localisation scheme is not only more costeffective than the range-base scheme, but also more robust.

When we implement typical range-free algorithms in Conference on Wireless Communications Networking and

Mobile Computing, Chengdu, China, pp.1-4. Hamida, E., Chelius, G., Gorce, J. ( 2008