【免费】无线传感器网络中基于多粒度区域划分和拉格朗日乘数法的节点定位算法资源-CSDN文库

需积分: 0 5 浏览量 2021-04-01 01:23:31 上传评论 1 收藏 5.13MB PDF 举报

资源详情

资源评论

资源推荐

sensors

Article

A Node Localization Algorithm Based on

Multi-Granularity Regional Division and the

Lagrange Multiplier Method in Wireless

Sensor Networks

Fengjun Shang *, Yi Jiang, Anping Xiong, Wen Su and Li He

College of Computer Science and Technology, Chongqing University of Posts and Telecommunications,

Chongqing 400065, China; jiangyi@cqupt.edu.cn (Y.J.); xiongap@cqupt.edu.cn (A.X.);

huahua718422@163.com (W.S.); heli@cqupt.edu.cn (L.H.)

* Correspondence: shangfj@cqupt.edu.cn; Tel.: +86-137-5287-1911

Academic Editor: Simon X. Yang

Received: 26 May 2016; Accepted: 8 November 2016; Published: 18 November 2016

Abstract:

With the integrated development of the Internet, wireless sensor technology, cloud

computing, and mobile Internet, there has been a lot of attention given to research about and

applications of the Internet of Things. A Wireless Sensor Network (WSN) is one of the important

information technologies in the Internet of Things; it integrates multi-technology to detect and

gather information in a network environment by mutual cooperation, using a variety of methods to

process and analyze data, implement awareness, and perform tests. This paper mainly researches the

localization algorithm of sensor nodes in a wireless sensor network. Firstly, a multi-granularity region

partition is proposed to divide the location region. In the range-based method, the RSSI (Received

Signal Strength indicator, RSSI) is used to estimate distance. The optimal RSSI value is computed by

the Gaussian ﬁtting method. Furthermore, a Voronoi diagram is characterized by the use of dividing

region. Rach anchor node is regarded as the center of each region; the whole position region is

divided into several regions and the sub-region of neighboring nodes is combined into triangles

while the unknown node is locked in the ultimate area. Secondly, the multi-granularity regional

division and Lagrange multiplier method are used to calculate the ﬁnal coordinates. Because nodes

are inﬂuenced by many factors in the practical application, two kinds of positioning methods are

designed. When the unknown node is inside positioning unit, we use the method of vector similarity.

Moreover, we use the centroid algorithm to calculate the ultimate coordinates of unknown node.

When the unknown node is outside positioning unit, we establish a Lagrange equation containing

the constraint condition to calculate the ﬁrst coordinates. Furthermore, we use the Taylor expansion

formula to correct the coordinates of the unknown node. In addition, this localization method has

been validated by establishing the real environment.

Keywords: WSN; RSSI; Voronoi diagram; vector similar degrees; Lagrange

1. Introduction

Precision agriculture is one of the most promising application domains where wireless sensor

networks (WSN) may deliver a feasible or even optimal solution. Generally, wireless sensor networks

consist of a large number of densely deployed small sensor nodes with sensing, computation, and

wireless communication capabilities. Sensor nodes do not incorporate an infrastructure. They build

up a network autonomously, without any external guidance or supervision. Precision agriculture is a

crop and livestock production management system that uses a wireless sensor network to monitor

equipment ﬁeld positions to collect information. Precision agriculture technologies include equipment

Sensors 2016, 16, 1934; doi:10.3390/s16111934 www.mdpi.com/journal/sensors

Sensors 2016, 16, 1934 2 of 26

guidance and automatic steering, yield monitoring, variable rate input application, remote sensing,

in-ﬁeld electronic sensors, section and row control on planters, sprayers and fertilizer applicators, and

spatial data management systems. Variable rate fertilizer application allows crop producers to apply

different rates of fertilizer at each location across ﬁelds. The technology needed to accomplish variable

rate fertilization includes an in-cab computer and software with a ﬁeld zone application map, fertilizer

equipment capable of changing rates during operation, and the wireless sensor network.

The Internet of Things (IoT) will connect things and people using the Internet link. It adopts

intelligent recognition technology, computer communication technology, and the Internet as the core,

at the level of deep development and the formation of a network of objects in a communication process

to realize the exchange of information. Examples of its use are remote information management and

intelligent monitoring systems [

]. From 1999, the IOT has been researched by the Chinese Academy of

Sciences. Various engineering bodies in the country are using for IOT technology for deep exploration,

such as the establishment of a mobile networking operations center in 2006 in Chongqing and the

National Center for sensing information, established in 2009 and opened in Shanghai in 2010. IOT,

as part of networking in new industries [

], is one of the key national developments. Because the

sensor technology is mature and the government’s support is strong, intelligent transportation, security,

and home market have been integrated into the IOT technology. Moreover, a number of cities have

implemented the technology, so at present China’s IOT industry chain has been basically formed [

At the same time, cloud computing, big data, and the mobile Internet era have arrived. The current

Internet data transfer mode changes from the traditional form to the massive data association, but the

wide application of IOT promotes the development of cloud computing. Wireless sensor networks

represent an enabling technology for low-power wireless measurement and control applications.

The elimination of lead wires provides a signiﬁcant cost savings and creates improved reliability for

many long-term monitoring applications. Wireless sensor networks enable completely new capabilities

for measurement and control applications.

2. Related Works

The main function of a wireless sensor network is collecting data. In military reconnaissance

or trafﬁc monitoring, the location information of sensor nodes is the premise for the perception,

acquisition, and transmission of data. Unless they are associated with a particular position, these

data will lose their signiﬁcance [

]. There are many types of localization methods for WSN [

]

has. According to the methods of data acquisition, processing is mainly divided into the aspects

of distance, angle, time, etc. These methods acquire related positioning data by calculating and

obtaining location information. According to the information processing method, no matter what kind

of processing method, the aim is to convert the data to coordinate information, and ﬁnally complete

the positioning function. According to the method of information processing, it is mainly divided

into: range-based and range-free methods; single-hop and multi-hop algorithms; and distributed and

centralized algorithms.

According to the distance of nodes in the localization process, the wireless sensor network can

be divided into the positioning method based on measuring distance and the positioning method

without measuring distance. The distance-based localization method [

] is divided into two steps:

ﬁrstly, the information is measured by a certain method, and then the coordinates are calculated by

the measured information. The information measured includes the intensity value, the transmission

time (time of arrival, TOA), transmission time difference (time difference of arrival, TDOA), and

azimuth angle (angle of arrival TOA). Next the computing nodes’ ﬁnal position is used as the actual

measurement data. The range-free positioning method [

] is ﬁrstly used to determine the range of the

node, followed by a series of calculation methods to calculate the ﬁnal node position.

The RSSI location method [

] uses an RF (Radio Frequency) signal, with full use of the wireless

communication node. Positioning uses the wireless signal data of nodes with a loss relationship

between the node transmission power and the receiving node power. It may compute the wireless

Sensors 2016, 16, 1934 3 of 26

signal transmission power. According to the model of the wireless signal transmission loss, the distance

will be computed from the intensity data.

A TOA ranging method [

] can determine the node work starting time synchronization

and calculating signal propagation time according to the relationship between the known signal

propagation velocity and propagation time. Thus the distance of nodes is estimated by a time distance

formula, but time synchronization cannot be explicitly guaranteed; this method has very high hardware

requirements and its positioning effect is not ideal.

The TDOA location method [

] uses the signal propagation time difference between the sending

and receiving nodes to estimate the distance; the prerequisite for the application of this method is

that the nodes have the same properties and the propagation time of each signal must be the same,

otherwise the estimated distance value will be inaccurate.

The AOA location method [

] uses the angle and azimuth of neighboring nodes to determine

the relative position of the unknown node. If the hardware is not up to standard, or the power

consumption is too large, this method in the application process will be interfered with by various

factors, resulting in lower ﬁnal positioning accuracy.

The localization algorithm based on ranging method [

] mainly includes: three edge location

algorithm, triangulation location algorithm, maximum likelihood estimation method, etc. The existing

localization algorithms based on range-free methods include the centroid localization algorithm [

the DV-hop algorithm [

], the APIT algorithm [

], and the convex programming localization

algorithm [17].

Sensor network localization relies on a large number of nodes, which via self-organization

constitutes a wireless network system; the deployment of node location has a certain inﬂuence on the

positioning accuracy. In order to ensure wireless sensor network communication quality and node

localization efﬁciency as far as possible in a short period of time, the effective communication range

of the reference node and the target positioning need to be optimized. The division of the regional

positioning not only makes the positioning accuracy improve, but also reduces the multifarious repeat

positioning calculation process.

In the division of regional positioning algorithms, the related sequence positioning algorithm is

more classical and mainly includes the sequence of the localization method in WSN [

], the wireless

sensor network in the sequence location algorithm [

], the N-order optimal time alignment

method [20], and a Voronoi diagram of the WSN rank sequence localization method [21].

3. Multi-Granularity Region Partition Based on RSSI

In this paper, a multi-granularity [

] region partition method is proposed. Firstly, the location

method is chosen based on the received signal strength. Due to the ﬂuctuation of strength value, Gauss

ﬁtting is introduced to estimate the value of RSSI. Secondly, it introduces a Thiessen polygon [

] using

each anchor node as the center. The whole area is divided into a plurality of sub-regions, and the

sub-regions of the adjacent nodes are combined to form multiple triangles, locking the unknown node

into the ﬁnal area.

3.1. Ranging Method Based on RSSI

The distance measurement method based on the RSSI theory model includes the log normal

shielding model (Shadowing Model) and the free space propagation path-loss model. The free space

propagation path-loss model is not easy to use in actual environments, however, because it belongs

to the ideal state transfer model. It gives the energy consumption of the signal transmission distance

in an inﬁnite vacuum, with no inﬂuence from other factors. However, in practical application, the

transmission distance of the signal is not only non-linear, but also the interference from the signal

is not insigniﬁcant. Considering the inﬂuence factors of various kinds of reﬂection, scattering, and

occlusion in the practical application environment, the attenuation of the channel is similar to the log

normal distribution, and the Shadowing Model is more in line with the practical application.

Sensors 2016, 16, 1934 4 of 26

The Shadowing Model formula is as follows:

Loss = 32.44 + 10nlg(d) + 10nlg( f ), (1)

where

Loss

indicates the signal path energy consumption,

indicates signal transmission distance, the

unit is meter, n indicates the path-loss factor of the actual environment,

indicates the radio signal

power, and the unit is MHz.

The free space propagation path-loss model formula is as follows:

P(d) = P(d

) + 10nlg(

) + ε, (2)

where

P(d)

indicates the signal path-loss when the actual measurement distance is

; the unit is

dBm

P(d

)

indicates the signal path-loss when the actual measurement distance is

. The path-loss refers to

the absolute power and

indicates the path-loss factor. The loss factor has different values in different

environments.

indicates the shadowing factor, the standard deviation ranges from 4 to 10, and the

unit is dB. In this paper, the loss model of distance is d

= 1m, that is, ε ∼ N(0, δ

RSSI = P

− P(d) , (3)

where

indicates the signal transmitting power; the unit is

dBm

P(d)

indicates the signal path-loss

when the actual measurement distance is

RSSI

indicates the signal strength value when the receiving

node distance is d

. Using Equations (2) and (3), the following formula can be obtained:

RSSI = P(d) −10nlg(

). (4)

From the above formula, when

, the relationship between the intensity and the distance

is as follows:

d = 10

P(d) −RSSI

10n

. (5)

3.2. RSSI Data Processing Method

Each node repeatedly measures intensity and then collects a large number of test data as far

as possible to remove the error and the noise data. To obtain the optimal intensity data, the chosen

intensity data will use the wireless signal loss model to estimate the distance of the nodes.

3.2.1. Experimental Data Acquisition

The sensor network system used is from the WIRELESS DRAGON TECHNOLOGY COMPANY

(Chengdu, China). The node uses the CC2530 module, as shown in Figure 1. Its application

development environment uses Microsoft Visual Studio 2010. Data storage and operations use

Microsoft SQL Server 2008. The communication protocol uses the ZigBee protocol based on

IEEE 802.15.4.

In the experiment, the node receives the signal from the gateway transmission equipment.

The node records the signal strength values and sends the data packets to the gateway transmission

equipment. Intensity data is from different locations in the gateway node; in the whole process of the

experiments, the actual distance is around 25 m from gateway to node. If it exceeds the range, because

signal attenuation is too big, the measured RSSI value is not accurate. The application background of

node localization has no special value.

The Table 1 shows the strength value of four nodes in different positions. In the experiment,

the intensity data is 1000 sets. Statistics are performed on multiple datasets for each measurement node.

Sensors 2016, 16, 1934 5 of 26

Sensors 2016, 16, 1934 4 of 27

where

Loss

indicates the signal path energy consumption,

indicates signal transmission

distance, the unit is meter, n indicates the path-loss factor of the actual environment,

indicates

the radio signal power, and the unit is MHz.

The free space propagation path-loss model formula is as follows:

() ( ) 10lg( )

Pd Pd n



 

(2)

where

)(

indicates the signal path-loss when the actual measurement distance is

; the unit is

dBm

)(

indicates the signal path-loss when the actual measurement distance is

d . The path-

loss refers to the absolute power and

indicates the path-loss factor. The loss factor has different

values in different environments.

indicates the shadowing factor, the standard deviation ranges

from 4 to 10, and the unit is

. In this paper, the loss model of distance is md 1=

, that is,

),0(~

δNε

()

SSI P P d

(3)

where

indicates the signal transmitting power; the unit is

dBm

)( dP

indicates the signal

path-loss when the actual measurement distance is

RSSI

indicates the signal strength value

when the receiving node distance is

d . Using Equations (2) and (3), the following formula can be

obtained:

() 10lg( )

RSSI P d n



(4)

From the above formula, when

md 1=

, the relationship between the intensity and the distance

is as follows:

()

d RSSI





(5)

3.2. RSSI Data Processing Method

Each node repeatedly measures intensity and then collects a large number of test data as far as

possible to remove the error and the noise data. To obtain the optimal intensity data, the chosen

intensity data will use the wireless signal loss model to estimate the distance of the nodes.

3.2.1. Experimental Data Acquisition

Figure 1. Sensor network node.

Table 1. RSSI measurement range of four nodes at different distances.

Distance (m) Node 1 Node 2 Node 3 Node 4

1 89~100 106~109 64~89 92~112

1.4 72~75 75~81 56~58 72~78

2 72~78 50~58 61~64 44~56

2.2 56~64 64~70 42~47 36~44

3 28~47 58~64 44~64 36~53

3.2 14~33 72~75 64 22~33

4 72 75~81 67~72 39~50

4.5 50~64 0~50 44~61 75~78

3.2.2. Experimental Data Acquisition

The RSSI data can be approximated by a normal distribution. The curve of the peak shows the

locations of the optimal RSSI values and the corresponding distance d is regarded as the optimal

distance. From the experimental data, we can see that the RSSI data are in line with the normal

distribution. In this paper the Gauss ﬁtting method is used to select the optimal RSSI value. The Gauss

ﬁtting function is as follows:

f (x) = a ∗ e

−(x−b)

, (6)

where parameter value b =

∑

i=1

RSSI

, c =

∑

i=1

(RSSI

−b)

n−1

In the above formula, a is constant and greater than 0, b is the average strength value, and c equals

the standard deviation. In this paper, we use four nodes to carry out multiple sets of measurements.

Figure 2 gives the RSSI ﬁtting curve of Node 4 at 1 m, 2 m, 3 m, and 4 m, respectively, where the

abscissa is the RSSI value and the ordinate is the probability value.

3.2.3. Wireless Signal Transmission Loss Model

By obtaining the optimal intensity value, the distance is estimated using the wireless signal loss

model. According to

n =

P(d) −RSSI

10lg(

)

, it can be seen that the environmental factor indicates the degree

of loss in the actual transmission, and the numerical value of the signal varies with the change in the

distance. Table 2 gives the n calculation results when the distance is 1.4 m, 2.2 m, 3.2 m, and 4.5 m.

剩余25页未读，继续阅读

评论收藏

内容反馈

weixin_38623919

粉丝: 5
资源: 929

无线传感器网络中基于多粒度区域划分和拉格朗日乘数法的节点定位算法

评论0

最新资源

无线传感器网络中基于多粒度区域划分和拉格朗日乘数法的节点定位算法

评论0

论文研究-基于区域划分的无线传感器网络生命周期路由算法.pdf

基于节点划分的无线传感器网络自适应分簇算法* (2008年)

基于区域划分的煤矿井下无线传感器网络定位算法

网络游戏-基于网格划分的水下无线传感器网络多维优化节点部署方法.zip

基于地理位置划分的无线传感器网络分簇算法 (2010年)

条件极值与拉格朗日乘数法

Lagrange_Multipliers-master_不等式约束_拉格朗日_拉格朗日乘数法_拉格朗日约束_拉格朗日乘数_

Lagrange_201811020_lagrange_matlab_拉格朗日乘数_

[Math & Algorithm]拉格朗日乘数法.pdf

基于基站划分网格的无线传感器网络分簇算法_衣晓1

电力移动巡检中基于区域划分的无线传感器安全通信及防泄密定位技术

matlab 拉格朗日法

【机器学习6】python实现拉格朗日乘子法

增广拉格朗日乘子法ALM算法matlab代码

论文研究-应用拉格朗日乘数法的多电压低功耗调度方法.pdf

基于拉格朗日乘数法的井下闭合导线加测陀螺边优化模型.docx

利用Lagrange乘数法来证明几个著名的不等式

条件极值与拉格朗日乘数法.pdf

条件极值与拉格朗日乘数法.doc

条件极值及拉格朗日乘数法.doc

代码 拉格朗日插值算法 代码 拉格朗日插值算法

多元函数求极值拉格朗日乘数法.doc

拉格朗日乘子法-fmincon,拉格朗日乘子法原理,matlab源码.zip

拉格朗日乘数法在消费者均衡原则中的应用.doc

lagelangri.rar_lagrange multiplier_saddlefx4_乘子法约束_拉格朗日_拉格朗日乘数

多元函数求极值(拉格朗日乘数法).doc

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

最新资源

代码拉格朗日插值算法代码拉格朗日插值算法

Qt 5实现串口调试助手（源工程文件、0积分下载）