File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: Solutions for wireless sensor network localization
Title  Solutions for wireless sensor network localization 

Authors  
Advisors  Advisor(s):Pang, GKH 
Issue Date  2012 
Publisher  The University of Hong Kong (Pokfulam, Hong Kong) 
Citation  Qiao, D. [乔大鹏]. (2012). Solutions for wireless sensor network localization. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4784953 
Abstract  Wireless sensor network localization opens the door to many location based applications. In
this thesis, some solutions obtained from localization algorithms are investigated. There are
two categories of problem on localization. Rangebased methods are applied to the situation
in which information on the distances between each pair of nodes is available. Algorithms are
developed to estimate the location of each sensor in the network. Usually, the distance
between each pair of nodes is estimated by the signal strength received between them, and
this information is very noisy. Rangefree methods, which are also called connectivitybased
methods, assume that the distances between any two nodes are unknown but the connectivity
information between them is known. If the distance between any two nodes in the network is
within a communication range, connectivity between these two nodes is said to be established.
In a rangebased scenario, with the information of intersensor distance measurements as
well as the absolute locations of the anchors, the objective is to obtain the location of all the
unknown nodes. Two new localization methods based on gradient descent are shown in the
thesis. The gradient descent methods would minimize the difference between the measured
distances and the distances obtained from the estimated locations. From a comparison with
other wellknown localization methods, the two newly developed gradient descent algorithms
can reach better accuracy at the expense of computational complexity. This is not surprising
as the proposed algorithms are iterative in nature.
For rangefree scenario, a new model utilizing all the information derived from
connectivitybased sensor network localization is introduced. Unlike other algorithms which
only utilize the information on connections, this model makes use of both information on
connections and disconnections between any pair of nodes. The connectivity information
between any pair of nodes is modeled as convex and nonconvex constraints. The localization
problem is solved by an optimization algorithm to obtain a solution that would satisfy all the
constraints established in the problem. The simulation has shown that better accuracy is
obtained when compared with algorithms developed by other researchers.
Another solution for the rangefree scenario is obtained with the use of a twoobjective
evolutionary algorithm called Pareto Archived Evolution Strategy (PAES). In an evolutionary
algorithm, the aim is to search for a solution that would satisfy all the convex and nonconvex
constraints of the problem. The number of wrong connections and the summation of
corresponding distances are set as the two objectives. A starting point on the location of the
unknown nodes is obtained using a solution from the result of all convex constraints. The
final solution can reach the most suitable configuration of the unknown nodes as all the
information on the constraints (convex and nonconvex) related to connectivity have been
used. From the simulation results, a relationship between the communication range and
accuracy is obtained.
In this thesis, another evolutionary algorithm has been examined to obtain a solution for
our problem. The solution is based on a modified differential evolution algorithm with
heuristic procedures peculiar to our domain of application. The characteristics of the sensor
network localization are thoroughly investigated and utilized to produce corresponding
treatment to search for the reasonable node locations. The modified differential evolution
algorithm uses a new crossover step that is based on the characteristics of the problem. With
the combination of some heuristics, the solution search can move the node to jump out of
local minimums more easily, and give better accuracy than current algorithms.
In the last part of the thesis, a novel twolevel range connectivitybased sensor network
localization problem is proposed, which would enrich the connectivity information. In this
new problem, the information of the connectivity between any pair of nodes is either strong,
weak or zero. Again, a twoobjective evolutionary algorithm is used to search for a solution
that would satisfy all the convex and nonconvex constraints of the problem. Based on
simulations on a range of situations, a suitable range value for the second range is found. 
Degree  Doctor of Philosophy 
Subject  Wireless sensor networks. Location problems (Programming) 
Dept/Program  Electrical and Electronic Engineering 
Persistent Identifier  http://hdl.handle.net/10722/174511 
HKU Library Item ID  b4784953 
DC Field  Value  Language 

dc.contributor.advisor  Pang, GKH   
dc.contributor.author  Qiao, Dapeng.   
dc.contributor.author  乔大鹏.   
dc.date.issued  2012   
dc.identifier.citation  Qiao, D. [乔大鹏]. (2012). Solutions for wireless sensor network localization. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4784953   
dc.identifier.uri  http://hdl.handle.net/10722/174511   
dc.description.abstract  Wireless sensor network localization opens the door to many location based applications. In this thesis, some solutions obtained from localization algorithms are investigated. There are two categories of problem on localization. Rangebased methods are applied to the situation in which information on the distances between each pair of nodes is available. Algorithms are developed to estimate the location of each sensor in the network. Usually, the distance between each pair of nodes is estimated by the signal strength received between them, and this information is very noisy. Rangefree methods, which are also called connectivitybased methods, assume that the distances between any two nodes are unknown but the connectivity information between them is known. If the distance between any two nodes in the network is within a communication range, connectivity between these two nodes is said to be established. In a rangebased scenario, with the information of intersensor distance measurements as well as the absolute locations of the anchors, the objective is to obtain the location of all the unknown nodes. Two new localization methods based on gradient descent are shown in the thesis. The gradient descent methods would minimize the difference between the measured distances and the distances obtained from the estimated locations. From a comparison with other wellknown localization methods, the two newly developed gradient descent algorithms can reach better accuracy at the expense of computational complexity. This is not surprising as the proposed algorithms are iterative in nature. For rangefree scenario, a new model utilizing all the information derived from connectivitybased sensor network localization is introduced. Unlike other algorithms which only utilize the information on connections, this model makes use of both information on connections and disconnections between any pair of nodes. The connectivity information between any pair of nodes is modeled as convex and nonconvex constraints. The localization problem is solved by an optimization algorithm to obtain a solution that would satisfy all the constraints established in the problem. The simulation has shown that better accuracy is obtained when compared with algorithms developed by other researchers. Another solution for the rangefree scenario is obtained with the use of a twoobjective evolutionary algorithm called Pareto Archived Evolution Strategy (PAES). In an evolutionary algorithm, the aim is to search for a solution that would satisfy all the convex and nonconvex constraints of the problem. The number of wrong connections and the summation of corresponding distances are set as the two objectives. A starting point on the location of the unknown nodes is obtained using a solution from the result of all convex constraints. The final solution can reach the most suitable configuration of the unknown nodes as all the information on the constraints (convex and nonconvex) related to connectivity have been used. From the simulation results, a relationship between the communication range and accuracy is obtained. In this thesis, another evolutionary algorithm has been examined to obtain a solution for our problem. The solution is based on a modified differential evolution algorithm with heuristic procedures peculiar to our domain of application. The characteristics of the sensor network localization are thoroughly investigated and utilized to produce corresponding treatment to search for the reasonable node locations. The modified differential evolution algorithm uses a new crossover step that is based on the characteristics of the problem. With the combination of some heuristics, the solution search can move the node to jump out of local minimums more easily, and give better accuracy than current algorithms. In the last part of the thesis, a novel twolevel range connectivitybased sensor network localization problem is proposed, which would enrich the connectivity information. In this new problem, the information of the connectivity between any pair of nodes is either strong, weak or zero. Again, a twoobjective evolutionary algorithm is used to search for a solution that would satisfy all the convex and nonconvex constraints of the problem. Based on simulations on a range of situations, a suitable range value for the second range is found.   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.rights  Creative Commons: AttributionNonCommerical 3.0 Hong Kong License   
dc.source.uri  http://hub.hku.hk/bib/B47849538   
dc.subject.lcsh  Wireless sensor networks.   
dc.subject.lcsh  Location problems (Programming)   
dc.title  Solutions for wireless sensor network localization   
dc.type  PG_Thesis   
dc.identifier.hkul  b4784953   
dc.description.thesisname  Doctor of Philosophy   
dc.description.thesislevel  Doctoral   
dc.description.thesisdiscipline  Electrical and Electronic Engineering   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.5353/th_b4784953   
dc.date.hkucongregation  2012   