Abstract: The study proposed a new weighted least-square method and it is introduced to the localization process of sensor networks. DV-HOP algorithm can be improved based on this novel method. In this paper, the matrix condition number is introduced to adjust the weight of several functional in weighted least-square method. The coefficients are decided in a nonlinear optimization problem and it is difficult to get the best solution. A second best solution can be obtained easily by our method. The method is applied to solve two-dimensional Poisson problems and the results show it is valuable and is advantageous to similar problems. Efficiency and stability of the algorithm is proved in several numerical examples. The simulation results show that the proposed improvements can greatly enhance the localization accuracy of the nodes.
INTRODUCTION
The rapid development of Wireless Sensor Networks (WSNs) brings pervasive computation to many applications (Akyildiz et al., 2007; Xiao et al., 2009; Cao et al., 2007). Consequently, attackers have more incentive to take control of one or more sensors and launch active attacks to break networks, such as eavesdropping, intercepting, injecting and tampering. Some security mechanisms have been adopted to guarantee data authentication (Bohge and Trappe, 2003), integrity and confidentiality. These existing security techniques (Karlof et al., 2004; Perrig et al., 2001), however, are inadequate. We are working on seeking novel and more effective measures to prevent communication vulnerabilities being exposed by any means. In the applications of the wireless sensor network, the nodes are usually arranged randomly in different environments to monitor various tasks, mutual coordinating by the way of self-organization. For example, aircraft throw, through such means the nodes were deployed in the network region. But the positions of the nodes in the monitoring region are unknown. While in the practical application, such as fire monitoring, battlefield surveillance, ecological environment monitoring, earthquake flood and fire scenario monitoring, the physical position of the nodes are needed, so that we could know the exact location of the sources of the information. That is to say the data collected by the nodes can’t be meaningful unless it is integrated with its own location information, so the sensor nodes must be able to conduct real-time positioning (Deng and Fan, 2000). Only when the positions of the sensor nodes are determined, we can determine the incidents’ specific location which are monitored by the sensor nodes, as well as control the incidents. Therefore in the sensor network, the node self-positioning is the premise of providing location information of the monitoring events, which plays a very important role to the entire network application’s validity.
Moreover, the foreknowledge of the node location information can also be used to improve the efficiency of the routing (Hui-Feng et al., 2007; Fubao et al., 2009), achieve the network topology configuration (Sundar and Sanjay, 2005), position and track of the external goal, balance network load and improve network coverage quality and so on. As node self-positioning is the foundation of the wireless sensor network, the localization algorithm must reduce the cost as far as possible to obtain a satisfaction result. Taking the localization algorithm performance indicators in to account, each kind of localization algorithm must reduce the power consumption, hardware costs and running costs as much as possible. In recent years, centered on the localization of the sensor nodes, has put forward a number of ways, such as MDS-MAP algorithm (Akyildiz et al., 2002; Shang et al., 2004), ABC algorithm, DHL algorithm, PDM algorithm, PRAL algorithm, etc. The DV-HOP algorithm this paper studied is a kind of the APS distributed positioning system (Niculescu and Nath, 2003), it is mainly dependent on the distance vector routing protocol localization. This algorithm realizes simply, regarding the hardware environment which support is limited is a good choice. The simulation testing indicated that: in the isotropic network which average connectivity is 10, anchor node proportion is 10%, the algorithm’s average positioning accuracy can reach 33% (Fubao et al., 2009), it’s sufficient for the localization application of wireless sensor network. However, this algorithm has certain error on calculating the distance between unknown node and anchor node, in order to improve this point, we proposed an improved method based on the weighted jump to enhance the positioning accuracy. Combined with finite element method is the most widely applied in various fields and effective numerical method, but it is in solving large deformation problems encountered difficulties and the grid generation of complex structures is difficult and time-consuming (Kang-Zu et al., 2000). In recent years the rise of non-grid method (Belytschko et al., 1996) is a node-based numerical method can effectively overcome these shortcomings. The existing non-grid method is based on the basic Galerkin method such as EFG (Wei-Yuan and Xiadong, 1998), PUM, Hp-Clouds, MLPG (Atluri and Zhu, 1998), etc. and the collocation method such as SPH (Zhang, 1996), FPM, PCM, etc. Galerkin Method based on Meshless method requires numerical integration to calculate the amount of large and to introduce the background grid (Zhang and Liu, 2004). Collocation method based on the non-grid method does not require integration, calculate the amount of small, but low precision and stability of the poor. Xing et al. (2003) put forward mesh-free weighted least-squares method (MWLS) solves this problem.
This study analyses the error functional of weighted least-square method with several penalty functions. Based on this a nonlinear optimization problem about matrix condition numbers is proposed to minimize the functional. The computations of matrix condition number with variants are huge and the best solution is difficult to obtain. An improvement for obtaining a second solution is proposed. This better weighted least-square method is inspected and verified in several numerical examples.
WSNs are limited in computational resources, battery and communication capabilities. Existing method based approaches including message authentication, integrity insurance and broadcast validation. Several approximate algorithms have been proposed in the scheduling problem, including broadcast scheduling (Weike, 2006; Sundar and Sanjay, 2005) and link scheduling (Al-Karaki and Kamal, 2004; Hui-Feng et al., 2007). Broadcast and link scheduling are time slot assignments to nodes and links, respectively. Ramaswami and Parhi (1999) presented an efficient and interference-free centralized and distributed broadcast scheduling in a multi-hop packet radio network. The broadcast scheduling problem was modeled as a distance-coloring problem by Sundar and Sanjay (2005) and Coja-Oghlan et al. (2006) proposed approximation heuristic algorithms for various geometric graphs. Ngo et al. presented a centralized genetic-fixed algorithm to reducethe search space based on a within-two-hop matrix. However, the performance of broadcast scheduling is worse than link scheduling in WSNs, especially in terms of energy conser-vation. In the broadcast scheduling, when a node wants to transmit, all the neighbors have to turn on their radio and start up, no matter whether they are the intended receiver or not. The previous studies in the general scheduling did not consider the energy consumption of radio in the state transition. Compared to broadcast scheduling and link scheduling, the contiguous link scheduling could reduce the frequency that sensor nodes start up and thus achieve better energy efficiency.
Moving least-square approximation method:
Moving Least-Squares approximation (MLS) is a weighted least-squares method
to approximate the function of a field method (Xiong et
al., 2003). In the domain Ω, set function u(x), solving domain-based
functions in N nodes, xI(I = 1,2,...,N) of the function values uI
= u(xI) are known, construction of its neighborhood Ω of points
x in the calculation of local approximation for:
| (1) |
pi(x) is a basic function, ai(x) is the undetermined coefficient.
Function is commonly used by individual style, may also be other functions. Such as the base for two-dimensional quadratic monomial. Monomial basis functions commonly used, may also be other functions. Such as the base for two-dimensional quadratic monomial p(x) = [1,x,y,x2,xy,y2]T.
Solving the region Ω will be carried out with N discrete nodes in each node xI to define, a weight function d is support domain radius.
This function is compactly supported, that is greater than zero in the support domain Ω and in the extraterritorial zero. Gaussian weight function, that is
is a constant.
Let approximate the function uh(x) at these nodes as the weighted
sum of squared errors:
| (2) |
This functional check is extremely small, from the maximum principle:
| (3) |
then
| (4) |
(4) changed as:
| (5) |
To solve this system of linear equations have:
| (6) |
Namely, the moving least square approximation (MLS). Let r(x)T = p(x)T A-1(x), then Sharp function:
| (7) |
Shape function of the first and second derivative, respectively,
| (8) |
where, subscript i indicates that the derivative of the space coordinates xi. The derivative of r:
| (9) |
As the weight function of compact support of, the above calculation of power function values are only non-zero nodes.
Meshless better weighted least-squares method for solving poisson equation:
Meshless weighted least-squares method as a new and efficient meshless method,
the basic idea is to use moving least-squares method to construct the approximate
function, the use of penalty function method to impose boundary conditions and
the following substituted into the governing equations and boundary conditions,
are residual equation and through the weighted least-squares method to eliminate
residual (Zhang et al., 2001).However, the determination
of penalty function is actually an optimization problem, this paper comprehensive
consideration and solution of the calculation results based on the difficulty
to establish meshless better weighted least-squares method (MBWLS).Consider
the following two-dimensional poisson equation:
| (10) |
Let Eq. 6 substitute:
| (11) |
To solve Eq. 11, construct the following energy functional:
| (12) |
α, β is penalty function, By the maximum principle functional:
| (13) |
In order to avoid calculation of points, usually in the following discrete form:
| (14) |
Then be calculated Format Ku = P:
| (15) |
In the traditional least-squares non-grid method, its equations and boundary conditions of the residual value of the residual value α, β of the weights are determined according to matrix
Order of magnitude is to be carried out, namely:
| (16) |
However, the stability of the equations play a decisive role in the condition number of coefficient matrix, so, there are actually needed to solve the following problems. Finding α*, β* and let:
| (17) |
However, it is difficult to calculate the condition number of matrix K = K (α, Β) and extreme values is also difficult to be obtained. So, the second best solution is to be considered. Calculated the following variance of:
| (18) |
The extreme condition can be denoted by:
| (19) |
It is easy to obtain extreme pointsα', Β'.
Numerical example: There is a two-dimensional Poisson problem:
| (20) |
where, Ω = [-1,1]x[-1,1]. The exact solution is
and the space step is set to be 0.1. The quadratic monomial is taken as the base function and the support domain radius is set to be 3. Penalty functions α and β are calculated according to Eq. 19.
MBWLS is applied to calculate the numerical solution uh(-0.1, y) which is compared with the finite element (FEM) solutions uF(-0.1, y) and exact solutions u(-0.1, y) in Table 1.
From the above mentioned, the MBWLS numerical solutions uh(-0.1, y) are more exact than the FEM solution uF(-0.1, y) on most of nodes, but not all. And it also can be found that the MBWLS solution is more stable than the FEM solution. As shown in Table 1, the maximum relative error of FEM solution is 1.48%, while the maximum relative error of MBLWS solution has been reduced to 0.76%. Numerical solution of surface and error surface of FEM are shown in Fig. 1, respectively, the surfaces of proposed method are shown in Fig. 2.
| Table 1: | Comparison of MBWLS solution with FEM solution, exact solution |
| Fig. 1: | FEM numerical solution uF(x, y) and error eF(x, y) |
| Fig. 2: | MBWLS numerical solution uh(x, y) and error eh(x, y) |
CONCLUSION
In this study, as can be seen, a novel weighted least-square method is proposed. In this method, the matrix condition numbers are introduced to adjust the coefficients of the error functional. More exactly, a optimization problem based on the condition numbers is provided to decide the coefficients. Considering the computation complexity and efficiency, an effective algorithm is proposed to obtain the second best solution. This method is applied to solve two-dimensional Poisson problems. Results show that our method is valuable and advantageous to similar problem. Efficiency and stability of the algorithm is proved in several numerical examples. The simulation results show that the proposed improvements can greatly enhance the localization accuracy of the nodes. However, accurately measure of the impact of penalty functions on the stability and accuracy should be researched advancely.
ACKNOWLEDGMENTS
This study is supported by National Basic Research Program of China (973 Program, No. 2006CB303000), National High Technology Research and Development Program of China (863 Program, No. 2007AA01Z180), National Natural Science Foundation of China (No. 60573045 and 60873198).