CN103068020B - The acquisition method of mobile data in wireless sensor network - Google Patents
The acquisition method of mobile data in wireless sensor network Download PDFInfo
- Publication number
- CN103068020B CN103068020B CN201310022128.3A CN201310022128A CN103068020B CN 103068020 B CN103068020 B CN 103068020B CN 201310022128 A CN201310022128 A CN 201310022128A CN 103068020 B CN103068020 B CN 103068020B
- Authority
- CN
- China
- Prior art keywords
- node
- mobile
- meeting point
- overlay
- sensor network
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims abstract description 34
- 230000005540 biological transmission Effects 0.000 claims abstract description 30
- 238000010586 diagram Methods 0.000 claims abstract description 20
- 230000003068 static effect Effects 0.000 claims description 51
- 229910052799 carbon Inorganic materials 0.000 claims description 6
- 238000005457 optimization Methods 0.000 claims description 4
- CURLTUGMZLYLDI-UHFFFAOYSA-N Carbon dioxide Chemical compound O=C=O CURLTUGMZLYLDI-UHFFFAOYSA-N 0.000 description 4
- 238000005516 engineering process Methods 0.000 description 3
- 229910002092 carbon dioxide Inorganic materials 0.000 description 2
- 239000001569 carbon dioxide Substances 0.000 description 2
- 230000007423 decrease Effects 0.000 description 2
- 230000009191 jumping Effects 0.000 description 2
- 238000013480 data collection Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000005265 energy consumption Methods 0.000 description 1
- 239000000203 mixture Substances 0.000 description 1
- 230000001568 sexual effect Effects 0.000 description 1
- 239000002699 waste material Substances 0.000 description 1
- XLYOFNOQVPJJNP-UHFFFAOYSA-N water Substances O XLYOFNOQVPJJNP-UHFFFAOYSA-N 0.000 description 1
Classifications
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D30/00—Reducing energy consumption in communication networks
- Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks
Landscapes
- Mobile Radio Communication Systems (AREA)
Abstract
The present invention discloses in a kind of wireless sensor network the acquisition method of mobile data, including: A, based on the accessibility between node, obtains the overlay node collection group of wireless sensor network.B, according to described overlay node collection group, utilize GST algorithm to obtain the GST of a minimum length, it is assumed that for T.C, based on T, from mobile meeting point be, it is thus achieved that an Euler diagram G'.D, to move meeting point as starting point, utilize Depth Priority Algorithm, obtain an Eulerian path G of Euler diagram G' ".E, based on Eulerian path G ", from mobile meeting point v0Set out, it is thus achieved that a hamiltonian circuit P, and as mobile meeting point v0Mobile data acquisition path.The present invention can reduce the energy expenditure of mobile data acquisition interior joint, improves reliability and the practicality of wireless sensor network of packet transmission.
Description
Technical field
The present invention relates to wireless sensor network technology field, particularly relate to a kind of wireless sensor network moves
The acquisition method of dynamic data.
Background technology
At present, data collection problems is to study one of the most extensive problem in wireless sensor network, it is, in general, that
One wireless sensor network disposed is by one group of wireless sensing node (generally being provided electric power by battery)
Composition, each wireless sensing node is equipped with some different types of sensor such as temperature sensors, wet
Degree sensor etc..Generally, a sensor node disposed has its fixing position, and it is to surrounding enviroment
It is sampled, then packet is jumped by one or multi-hop transmission is to predefined meeting point.But, examine
Consider the size to the wireless sensor network scale disposed.Such as, in the wireless biography for detecting carbon dioxide
In sensor network, two adjacent sensor nodes (i.e. they are adjacent in the range of jumping) are due to road
By selecting and the difference of task scheduling, the task quantity of execution can mutually far short of what is expected times.This on the one hand will directly
The node energy causing " crucial " consumes quickly, reduces the life-span of network.On the other hand, network is worked as
In data acquisition node the packet of collection is pooled to meeting point during, due to network congestion, also can
Directly result in abandoning and loss situation of packet.Such as, at the wireless senser for detecting carbon dioxide
In network, about 20% packet to transmit more than 15 jumpings before arriving meeting point.Obviously, the number of loss
Transmit the longest distance according to bag, result in the waste of Internet resources.Although packet in restriction network
The life cycle of forwarding can alleviate this situation, but the life cycle that packet forwards reasonably is set
It it is a relatively difficult problem.
In another application scheme of wireless sensor network, one group of sensor node is deployed in forest
Fixing position, they are monitored surrounding enviroment, and periodically gather data and store the data of all localities.
Some forest management persons carry portable equipment and cruise in forest according to the route designed, when they arrival portions
Time in the transmission range of some sensing nodes of administration, portable equipment will directly gather data.Such
In application, be deployed in the wireless sensor network of external environment condition especially for some, sensor node can
Access sexual needs think over, and such as, some sensor nodes may be deployed in water, or steep cliff periphery,
Or deathtrap that can not be the most close for forest management person.Therefore, if some nodes can not
Enough it is directly adjacent to (their data cannot directly obtain in other words), then need exist for other nodes and bear
The responsibility of packet is forwarded for them.
Additionally, (such as, the wireless sensor network interior joint at anisotropic is likely to be of different performances
Different buffer size, different calculating and transmittability etc.), even at the wireless sense network of isotropic
In, after sensor node is deployed and runs a period of time, perhaps they have different dump energies.
Under the circumstances, should allow in theory performance preferably some nodes (have more available energy,
Bigger caching, longer transmission range etc.) undertake more data forwarding responsibility.Above-mentioned several situation exists
The mobile data acquisition of traditional wireless sensor networks generally exists, if solve bad will be direct
Cause the high energy consumption of sensor node, the reliability reducing packet transmission and whole wireless sensor network
Practicality.
Summary of the invention
For above-mentioned technical problem, it is an object of the invention to provide mobile number in a kind of wireless sensor network
According to acquisition method, it can reduce the energy expenditure of mobile data acquisition interior joint, improve packet
The reliability of transmission so that wireless sensor network more practicality.
For reaching this purpose, the present invention by the following technical solutions:
In a kind of wireless sensor network, the acquisition method of mobile data, makes wireless sensor network interior joint
Set V={v0,v1,v2,...,vn, wherein, v0For mobile meeting point, v1,v2,...,vnFor static node；When
Do not consider static node viWith mobile meeting point v0Between data transmission distance r time, obtain mobile meeting point v0's
The method in mobile data acquisition path specifically includes following steps:
A, based on the accessibility between node, obtain overlay node collection group C of wireless sensor network, its
In, 1≤i≤n, C={Cv0,Cv1,...,Cvn, Cv0For mobile meeting point v0Overlay node collection, Cv1,...,Cvn
For static node v1,v2,...,vnCorresponding overlay node collection；
B, according to described overlay node collection group C, utilize GST (Group Stennier Tree) algorithm to obtain
The GST of one minimum length, it is assumed that for T, wherein, T has been at least connected with each in overlay node collection group C covering
A node in lid set of node, T=(VT,ET), VT=V' ∩ V ", V' is the set of all static nodes on T,
V is " for the set of Steiner node additional on T, ETSet for limits all on T；
C, based on T, from mobile meeting point v0For setting out, it is thus achieved that an Euler diagram G', wherein, described Euler diagram G'
Refer to: from mobile meeting point v0Set out, the once and the most just all joints on T of each edge on traversal T
The loop of point；
D, to move meeting point v0For starting point, utilize Depth Priority Algorithm (Depth First Search,
DFS), an Eulerian path G of Euler diagram G' is obtained "；
E, based on Eulerian path G ", from mobile meeting point v0Set out, it is thus achieved that a hamiltonian circuit P
(Hamiltonian cycle), and using this hamiltonian circuit P as moving meeting point v0Mobile data acquisition
Path, wherein, the forming process of described hamiltonian circuit P is as follows: based on Eulerian path G ", converge from mobile
Point v0Set out, only the static node in V' conducted interviews and only access once, and to V " in node do not enter
Row accesses, and obtains hamiltonian circuit P according to this.
Especially, when considering static node viWith mobile meeting point v0Between data transmission distance r time, obtain
Mobile meeting point v0The method in mobile data acquisition path specifically include following steps:
A, with step A, based on the accessibility between node, obtain the overlay node of wireless sensor network
Collection group C, wherein, 1≤i≤n, C={Cv0,Cv1,...,Cvn, Cv0For mobile meeting point v0Overlay node collection,
Cv1,...,CvnFor static node v1,v2,...,vnCorresponding overlay node collection；
If b ε meetsThen to static node collection { v1,v2,…vnAny node in }
vjCarry out for the circular boundary that the center of circle, data transmission distance r are radiusDecile, it is thus achieved that be positioned at circular boundary
OnIndividual dummy nodeWherein, ε is constant, and its big I is according to user
Be actually needed and be adjusted, | | Popt| | being the length in optimum mobile data acquisition path, n is wireless senser
The quantity of static node in network；
C, for each static node v in overlay node collection group CjAll with the dummy node of its correspondenceSubstitute, thus obtain new overlay node collection group G={Gv0,Gv1,...,Gvn, wherein,
|Gv0|=| Cv0|,
D, based on described new overlay node collection group G, utilize method identical in step B, C, D and E to obtain
Obtain minimum length GST, an Eulerian path G " and hamiltonian circuit P, and using this hamiltonian circuit P as shifting
The mobile data acquisition path of dynamic meeting point.
Especially, if node vjFor viOverlay node collection CviIn node, then node viPacket can
With from node vjCollect, namely: node vjFor node viOverlay node, node vjWith node viBetween
There is accessibility.
Especially, described based on the accessibility between node, obtain the overlay node of wireless sensor network
Collection group C, specifically includes:
A1, determine corresponding coverage condition according to actual application scenarios and optimization aim；
A2, for V={v0,v1,v2,...,vnAny node v in }i, search in V and meet described coverage condition,
Even if also coverage function Cov (vj,vi) equal to 1 all node vjSet Cvi, wherein, 0≤i≤n, 0
≤j≤n,CviIt is referred to as node viOverlay node collection；
A3, utilize described Cvi, it is thus achieved that overlay node collection group C of wireless sensor network, wherein, 0≤i≤n,
C={Cv0,Cv1,...,Cvn, Cv0For mobile meeting point v0Overlay node collection, its value is { v0, Cv1,...,Cvn
For static node v1,v2,...,vnCorresponding overlay node collection.
The present invention can select the most mobile data acquisition path for mobile meeting point, moves data acquisition according to this
Collection path completes the collection of mobile data, decreases the energy expenditure of mobile data acquisition interior joint, carries
The high reliability of packet transmission, and make wireless sensor network more practicality.
Accompanying drawing explanation
Fig. 1 provide for the embodiment of the present invention the first in the case of the adopting of mobile data in wireless sensor network
Diversity method flow chart；
Fig. 2 a provide for the embodiment of the present invention the first in the case of GST schematic diagram；
Fig. 2 b provide for the embodiment of the present invention the first in the case of Eulerian path G " schematic diagram；
Fig. 2 c provide for the embodiment of the present invention the first in the case of hamiltonian circuit P schematic diagram；
The collection path schematic diagram of based on addressable point the mobile data that Fig. 3 provides for the embodiment of the present invention；
The adopting of mobile data in wireless sensor network in the case of the second that Fig. 4 provides for the embodiment of the present invention
Diversity method flow chart；
The dummy node schematic diagram substituting static node that Fig. 5 provides for the embodiment of the present invention；
The demonstration exemplary plot that Fig. 6 provides for the embodiment of the present invention.
Detailed description of the invention
For making the object, technical solutions and advantages of the present invention clearer, below in conjunction with the accompanying drawings with embodiment pair
The present invention is described further.
Assume the set V={v of wireless sensor network interior joint0,v1,v2,...,vn, wherein, v0Converge for mobile
Point, v1,v2,...,vnFor static node.The most in two kinds of situation data mobile in wireless sensor network are adopted
Diversity method illustrates.
The first situation: do not consider static node viWith mobile meeting point v0Between data transmission distance r, it may be assumed that
When needs gather static node viPacket time, mobile meeting point v0Only move to static node viPlace
Geometric position just can collect this node data bag.It should be noted that, the first situation does not simply consider static state
Data transmission distance r between node and mobile meeting point, and the data transmission distance between static node is still
r.Described data transmission distance r refers to that static node can send the maximum distance of packet, and static node
Data transmission range be reduced to the border circular areas with r as radius at this.
Refer to shown in Fig. 1, Fig. 1 provide for the embodiment of the present invention the first in the case of wireless sensor network
The acquisition method flow chart of mobile data in network.
In the present embodiment, in wireless sensor network, the acquisition method of mobile data comprises the steps:
Step S101, based on the accessibility between node, obtain the overlay node collection of wireless sensor network
Group C, wherein, C={Cv0,Cv1,...,Cvn, Cv0For mobile meeting point v0Overlay node collection, Cv1,...,Cvn
For static node v1,v2,...,vnCorresponding overlay node collection.
Based on the accessibility between node, obtain overlay node collection group C concrete of wireless sensor network
Step is as follows:
Step S1011, determine corresponding coverage condition according to actual application scenarios and optimization aim.
Step S1012, for V={v0,v1,v2,...,vnAny node v in }i, search described in V meets
Coverage condition, though also coverage function Cov (vj,vi) equal to 1 all node vjSet Cvi, wherein,
0≤i≤n, 0≤j≤n, CviIt is referred to as node viOverlay node collection.
Coverage condition between two nodes is different according to actual application scenarios and the difference of optimization aim.Example
As, when we attempt the transmission range limiting packet, if meet coverage condition and depend between node
Euclidean distance or skip distance between them.If our purpose is to reduce packet in network
The transmission time, in coverage condition, an important index may be exactly the quality of connection between node.When needs one
A little performances are time more preferably node undertakes more responsibility in a network, and coverage condition will be the combination property of node
The quality of (such as, buffer size, bandwidth etc.) and current network condition.
Node vjWith node viBetween coverage function Cov (vj,vi) represent.As node vjWith node viIt
Between when meeting coverage condition, Cov (vj,vi) value equal to 1, otherwise, Cov (vj,vi) value equal to 0.
If Cov is (vj,vi) value equal to 1, then node viPacket can be from node vjCollect, namely: joint
Point vjFor node viOverlay node, node vjWith node viBetween there is accessibility.For
V={v0,v1,v2,...,vnAny node v in }i, search in V and meet described coverage condition, even if also covering
Function Cov (vj,vi) equal to 1 all node vjSet Cvi, wherein, 0≤i≤n, 0≤j≤n, Cvi
It is referred to as node viOverlay node collection.
Step S1013, utilize described Cvi, it is thus achieved that overlay node collection group C of wireless sensor network, wherein,
0≤i≤n, C={Cv0,Cv1,...,Cvn, Cv0For mobile meeting point v0Overlay node collection, its value is { v0,
Cv1,...,CvnFor static node v1,v2,...,vnCorresponding overlay node collection.
Step S102, according to described overlay node collection group C, utilize GST (Group Stennier Tree)
Algorithm obtains the GST of a minimum length, it is assumed that for T, wherein, T is at least connected with in overlay node collection group C
The node that each overlay node is concentrated, T=(VT,ET), VT=V' ∩ V ", V' is all static nodes on T
Set, V is " for the set of Steiner node additional on T, ETSet for limits all on T.
As shown in Figure 2 a, Fig. 2 a provide for the embodiment of the present invention the first in the case of GST schematic diagram.
Wherein, described GST (Group Stennier Tree) algorithm is quoted from document: CHARIKAR,
M.,CHEKURI,C.,GOEL,A.,ANDGUHA,S.Rounding via trees:deterministic
approximation algorithms for group steiner trees and k-median.In
Proceedings of the thirtieth annual ACM symposium on Theory of
computing(1998),ACM,pp.114-123。
Step S103, based on T, from mobile meeting point v0For setting out, it is thus achieved that an Euler diagram G', wherein, described
Euler diagram G' refers to: from mobile meeting point v0Setting out, each edge on traversal T is once and the most just all over T
The loop of upper all nodes.
Step S104, to move meeting point v0For starting point, utilize Depth Priority Algorithm (Depth First
Search, DFS), obtain an Eulerian path G of Euler diagram G' ".As shown in Figure 2 b, Fig. 2 b is this
Eulerian path G " schematic diagram in the case of the first of bright embodiment offer.
Step S105, based on Eulerian path G ", from mobile meeting point v0Set out, it is thus achieved that a hamiltonian circuit P
(Hamiltonian cycle), and using this hamiltonian circuit P as moving meeting point v0Mobile data acquisition
Path, wherein, the forming process of described hamiltonian circuit P is as follows: based on Eulerian path G ", converge from mobile
Point v0Set out, only the static node in V' conducted interviews and only access once, and to V " in node do not enter
Row accesses, and obtains hamiltonian circuit P according to this.As shown in Figure 2 c, Fig. 2 c provide for the embodiment of the present invention
A kind of hamiltonian circuit P schematic diagram in the case of.
It should be noted that obtain hamiltonian circuit P and mobile meeting point v by above-mentioned steps S101-S1050
Optimum mobile route PoptApproximation ratio be O (log2N*logt*loglogn), wherein, n is wireless biography
The quantity of static node in sensor network, t is the number of nodes of maximal cover set of node in overlay node collection group C.
The concrete process of argumentation is as follows:
Assume to integrate the optimum GST of group C acquisition as T based on overlay nodeopt, it is thus achieved that mobile meeting point v0Optimum
Mobile route is Popt.Because PoptIt is a hamiltonian circuit, so PoptT to be comparedoptMany limits
Length.We remove P nowoptA limit e, thus obtain one tree T', it is clear that the same T of T'optEqually,
It is at least connected with the node that in overlay node collection group C, each overlay node is concentrated.Due to ToptIt is optimum
GST, then can obtain:
||Topt| |≤| | T'| |=| | Popt||-||e||≤||Popt|| (1)
According to described overlay node collection group C, GST algorithm is utilized to obtain the GST of a minimum length.Use T
Represent GST, then have:
| | T | |=O (log2n*logt*loglogn)||Topt|| (2)
The detailed process of argumentation of formula (2) refer to GST algorithm literature cited.Again because of Eulerian path G "
That each edge to T all travels through twice and obtains, so Eulerian path G " length be the twice of T length,
That is: | | G " | |=2 | | T | |.And by triangle inequality, again it can easily be proven that the length of hamiltonian circuit P
Degree is less than G " length, it may be assumed that
| | P | |≤| | G " | |=2 | | T | | (3)
Comprehensively can be obtained by formula (1), (2), (3): | | P | |=O (log2n*logt*loglogn)||Popt||。
Hamiltonian circuit P and mobile meeting point v0Optimum mobile route PoptApproximation ratio be
O(log2N*logt*loglogn) must demonstrate,prove.
Mobile meeting point v is obtained in the case of first0The method in mobile data acquisition path, to second
The situation of kind is described in detail.
The second situation: consider static node viWith mobile meeting point v0Between data transmission distance r, it may be assumed that
When needs gather static node viPacket time, mobile meeting point v0Have only to move to static node viNumber
According in transmission range, and without moving to static node viThe geometric position at place.Simultaneously as it is quiet
The difference of the data transmission distance of state node has no effect on the realization of the present invention, therefore, and will not in the present embodiment
Consider the diversity of static node, the data transmission distance of all static nodes is all set to r.
First to hereafter will addressable point (access point) be defined.Addressable point: by
In node vjAt node viData transmission range in can receive node viPacket, now by permissible
Receive node viThe position of packet is referred to as node viAddressable point or data access point.Mobile meeting point v0Only
The addressable point of static node to be moved to just can collect the packet of node, and without moving to node
Geometric position.
As it is shown on figure 3, the collection of based on addressable point mobile data that Fig. 3 provides for the embodiment of the present invention
Path schematic diagram.Fig. 3 has two overlay node collection: the overlay node collection comprising node u is (with r in figure
Broken circle for radius) and comprise the overlay node collection (in figure broken circle) with r as radius of node v, and
And the two overlay node collection covers all of node in network, say, that: mobile meeting point v0Only by
The addressable point accessing node u and node v just can collect the packet of all nodes in network.P in figureu
Represent an addressable point of node u, pvRepresent an addressable point of node v.
As shown in Figure 4, in the case of the second that Fig. 4 provides for the embodiment of the present invention in wireless sensor network
The acquisition method flow chart of mobile data.
In the present embodiment, in wireless sensor network, the acquisition method of mobile data comprises the steps:
Step S401, with step S101, based on the accessibility between node, obtain wireless sensor network
Overlay node collection group C, wherein, C={Cv0,Cv1,...,Cvn, Cv0For mobile meeting point v0Overlay node
Collection, Cv1,...,CvnFor static node v1,v2,...,vnCorresponding overlay node collection.
Step S402, by all static nodes in overlay node collection group C all with one group of corresponding virtual joint
Point substitutes, it is thus achieved that new overlay node collection group G.Detailed process is as follows:
If step S4021 ε meetsThen to static node collection { v1,v2,…vnIn }
Any node vjCarry out for the circular boundary that the center of circle, data transmission distance r are radiusDecile, it is thus achieved that position
On circular boundaryIndividual dummy nodeWherein, ε is constant, and it embodies
The present embodiment obtains the time gathering path of mobile data, the accuracy rate etc. of mobile meeting point collection data, it
Big I be adjusted according to being actually needed of user, | | Popt| | it is the length in optimum mobile data acquisition path,
N is the quantity of static node in wireless sensor network.Clearly as dummy node is positioned at node data transmission
On the border of scope, so dummy node is also addressable point.
As it is shown in figure 5, node vjCan useIndividual dummy nodeSubstitute, figure is appointed
Anticipating, the arc length between two adjacent dummy nodes is ε, central angle is
Step S4022, for each static node v in overlay node collection group CjAll with the virtual joint of its correspondence
PointSubstitute, thus obtain new overlay node collection group G={Gv0,Gv1,...,Gvn, its
In, | Gv0|=| Cv0|,
Step S403, based on described new overlay node collection group G, utilize step S102, S103, S104
And identical method obtains minimum length GST, an Eulerian path G in S105 " and hamiltonian circuit P, and
Using this hamiltonian circuit P as the mobile data acquisition path moving meeting point.
In second, situation obtains minimum length GST, Eulerian path G " and the method for hamiltonian circuit P and first
Middle situation is compared, and is simply replaced with one group of corresponding dummy node by actual static node.
Obtain hamiltonian circuit P with the first situation identical, obtain Hami by above-mentioned steps S401-S404
Pause loop P and mobile meeting point v0Optimum mobile route PoptApproximation ratio be also
O(log2N*logt*loglogn), wherein, n is the quantity of static node in wireless sensor network, and t is
The number of nodes of maximal cover set of node in overlay node collection group C.
In order to prove hamiltonian circuit P and mobile meeting point v0Optimum mobile route PoptApproximation ratio be
O(log2N*logt*loglogn), first following argument is proved.
Argument: if optimum mobile route PoptOn addressable point be not all dummy node, then necessarily may be used
To find all mobile data acquisition path P that may have access to be dummy node, P is made to meet:
||P||≤||Popt||+2εn。
Demonstration: assume that optimum mobile route is Popt, node viWith node vjIt is PoptTwo accessed adjacent
Overlay node.As shown in Figure 6, in figureWithIt is respectively node
viWith node vjThe set of dummy node.PoptWith with node viIt is radius for the center of circle, data transmission distance r
The intersection point of circular boundary be a, PoptWith with node vjIt is the circle of radius for the center of circle, data transmission distance r
The intersection point on border is b, and assumes that intersection point a and intersection point b is not dummy node.So, we can look for
To such straight line, the length of this straight line no more than | | ab | |+2 ε, and this straight line summit
For node viA dummy node, another summit is node vjA dummy node.
Two end points of the circular arc that order comprises intersection point a are respectively dummy node vi 1And vi 2, comprise the circle of intersection point b
Two end points of arc are respectively dummy node vj 1And vj 2.We are from { vi 1, vi 2And { vj 1, vj 2Select respectively in }
(that select in Fig. 6 is v to one nodei 2And vj 2), owing to air line distance is the shortest between 2 o'clock, so straight line
vi 2vj 2Length be not more than straight line avi 2、ab、bvj 2Length sum, it may be assumed that
||vi 2vj 2||≤||ab||+||avi 2||+||bvj 2||≤||ab||+2ε (4)
Therefore, if we are at PoptIn use vi 2vj 2Substitute ab, PoptLength will at most increase 2 ε.When us
By PoptIn all straight lines of i.e. not using dummy node similar with ab, all with corresponding dummy node even
When the straight line connect replaces, the node on new mobile route P obtained will be dummy node entirely.Due to PoptIt is
One loop, and each overlay node is at most accessed once, therefore, for there being n static node
Network, PoptUpper be up to n bar limit, when to obtain described p, is the most also accomplished by replacing n bar limit.
According to above-mentioned conclusion, it is easy to get:
||P||≤||Popt||+2εn (5)
Above-mentioned argument must be demonstrate,proved.
We will be according to above-mentioned argument below, it was demonstrated that: the obtained mobile route of this method and mobile meeting point v0's
Optimum mobile route PoptApproximation ratio be also O (log2n*logt*loglogn)。
Prove: make according to described overlay node collection group C, utilize the GST use of the minimum length that GST algorithm obtains
T represents, and optimum GST is Topt.Identical with the first situation, have equally:
| | T | |=O (log2n*logt*loglogn)||Topt|| (6)
In this, it is assumed that obtaining degree loop, Hami based on described T is H, all | | H | |≤2 | | T | |, then combine
Formula (6), can obtain:
| | H | |≤2 | | T | |=(O (log2n*logt*loglog n))||Topt|| (7)
Assume the mobile meeting point v obtained based on overlay node collection group C0Optimum mobile route be Popt.According to upper
Review point can obtain: | | P | |≤| | Popt||+2εn.Obviously, if ε meetsThen can obtain:
| | P | |=O (1) | | Popt|| (8)
Because all addressable points on mobile route P are dummy node, can obtain:
||Topt| |≤| | P | |, in conjunction with formula (7), (8), it is easy to obtain:
| | H | |=O (log2n*logt*loglogn)||Popt||
So far, the hamiltonian circuit obtained in the second situation and mobile meeting point v0Optimum mobile route Popt
Approximation ratio be O (log2N*logt*loglogn) must demonstrate,prove.
The present invention can select the most mobile data acquisition path for mobile meeting point, decreases removable data
The energy expenditure of gatherer process interior joint, improves reliability and the wireless sensor network of packet transmission
Practicality.
Above are only presently preferred embodiments of the present invention and institute's application technology principle, any be familiar with the art
Technical staff in the technical scope that the invention discloses, the change that can readily occur in or replacement, all should contain
In protection scope of the present invention.
Claims (4)
1. the acquisition method of mobile data in a wireless sensor network, it is characterised in that make the set V={v of wireless sensor network interior joint0,v1,v2,...,vn, wherein, v0For mobile meeting point, v1,v2,...,vnFor static node；When not considering static node viWith mobile meeting point v0Between data transmission distance r time, obtain mobile meeting point v0The method in mobile data acquisition path specifically include following steps:
A, based on the accessibility between node, obtain overlay node collection group C of wireless sensor network, wherein, 1≤i≤n, C={Cv0,Cv1,...,Cvn, Cv0For mobile meeting point v0Overlay node collection, Cv1,...,CvnFor static node v1,v2,...,vnCorresponding overlay node collection；
B, according to described overlay node collection group C, GST (Group Stennier Tree) algorithm is utilized to obtain the GST of a minimum length, it is assumed that for T, wherein, T has been at least connected with the node that in overlay node collection group C, each overlay node is concentrated, T=(VT,ET), VT=V' ∩ V ", V' is the set of all static nodes, V on T " for the set of Steiner node additional on T, ETSet for limits all on T；
C, based on T, from mobile meeting point v0Setting out, it is thus achieved that an Euler diagram G', wherein, described Euler diagram G' refers to: from mobile meeting point v0Set out, the once and the most just loop of all nodes on T of each edge on traversal T；
D, to move meeting point v0For starting point, utilize Depth Priority Algorithm (Depth First Search, DFS), obtain an Eulerian path G of Euler diagram G' "；
E, based on Eulerian path G ", from mobile meeting point v0Set out, it is thus achieved that a hamiltonian circuit P (Hamiltonian cycle), and using this hamiltonian circuit P as moving meeting point v0Mobile data acquisition path, wherein, the forming process of described hamiltonian circuit P is as follows: based on Eulerian path G ", from mobile meeting point v0Set out, only the static node in V' conducted interviews and only access once, and to V " in node do not conduct interviews, obtain hamiltonian circuit P according to this.
The acquisition method of mobile data in wireless sensor network the most according to claim 1, it is characterised in that when considering static node viWith mobile meeting point v0Between data transmission distance r time, obtain mobile meeting point v0The method in mobile data acquisition path specifically include following steps:
A, with step A, based on the accessibility between node, obtain overlay node collection group C of wireless sensor network, wherein, 1≤i≤n, C={Cv0,Cv1,...,Cvn, Cv0For mobile meeting point v0Overlay node collection, Cv1,...,CvnFor static node v1,v2,...,vnCorresponding overlay node collection；
If b ε meetsThen to static node collection { v1,v2,…vnAny node v in }jCarry out for the circular boundary that the center of circle, data transmission distance r are radiusDecile, it is thus achieved that be positioned on circular boundaryIndividual dummy nodeWherein, ε is constant, and its big I is adjusted according to being actually needed of user, | | Popt| | being the length in optimum mobile data acquisition path, n is the quantity of static node in wireless sensor network；
C, for each static node v in overlay node collection group CjAll with the dummy node of its correspondenceSubstitute, thus obtain new overlay node collection group G={Gv0,Gv1,...,Gvn, wherein, | Gv0|=| Cv0|,1≤i≤n；
D, based on described new overlay node collection group G, " and the hamiltonian circuit P, and using this hamiltonian circuit P as the mobile data acquisition path of mobile meeting point that utilizes method identical in step B, C, D and E to obtain minimum length GST, an Eulerian path G.
3. according to the acquisition method of data mobile in the wireless sensor network described in any one of claim 1 or 2, it is characterised in that if node vjFor viOverlay node collection CviIn node, then node viPacket can be from node vjCollect, namely: node vjFor node viOverlay node, node vjWith node viBetween there is accessibility.
The acquisition method of mobile data in wireless sensor network the most according to claim 3, it is characterised in that described based on the accessibility between node, obtains overlay node collection group C of wireless sensor network, specifically includes:
A1, determine corresponding coverage condition according to actual application scenarios and optimization aim；
A2, for V={v0,v1,v2,...,vnAny node v in }i, search in V and meet described coverage condition, though also coverage function Cov (vj,vi) equal to 1 all node vjSet Cvi, wherein, 0≤i≤n, 0≤j≤n, CviIt is referred to as node viOverlay node collection；
A3, utilize described Cvi, it is thus achieved that overlay node collection group C of wireless sensor network, wherein, 0≤i≤n, C={Cv0,Cv1,...,Cvn, Cv0For mobile meeting point v0Overlay node collection, its value is { v0, Cv1,...,CvnFor static node v1,v2,...,vnCorresponding overlay node collection.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310022128.3A CN103068020B (en) | 2013-01-21 | 2013-01-21 | The acquisition method of mobile data in wireless sensor network |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310022128.3A CN103068020B (en) | 2013-01-21 | 2013-01-21 | The acquisition method of mobile data in wireless sensor network |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN103068020A CN103068020A (en) | 2013-04-24 |
| CN103068020B true CN103068020B (en) | 2016-12-28 |
Family
ID=48110439
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201310022128.3A Expired - Fee Related CN103068020B (en) | 2013-01-21 | 2013-01-21 | The acquisition method of mobile data in wireless sensor network |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN103068020B (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107295531A (en) * | 2017-07-25 | 2017-10-24 | 厦门理工学院 | A kind of wireless self-organization network covering method based on covering contribution |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103701705B (en) * | 2013-12-20 | 2017-02-22 | 河海大学常州校区 | Mobile sink data acquisition method based on binary tree inquiry in wireless sensor network |
| CN104168581B (en) * | 2014-09-05 | 2017-08-11 | 合肥工业大学 | The water surface movable base station path planing method of Wei Nuotu constructions |
| CN106209625B (en) * | 2016-07-15 | 2019-07-09 | 福州大学 | One kind supporting central controlled high efficiency method in distributed network |
| CN109347741B (en) * | 2018-08-01 | 2021-02-26 | 北京邮电大学 | Method and device for optimal traversal of the entire network path based on in-band network telemetry |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101778335A (en) * | 2009-01-14 | 2010-07-14 | 深圳市先进智能技术研究所 | Wearable monitoring system and method for community member monitoring |
| CN102098709A (en) * | 2010-11-04 | 2011-06-15 | 无锡泛联软件科技有限公司 | Gradient-based routing method in hybrid wireless sensor network |
| CN102573023A (en) * | 2011-11-18 | 2012-07-11 | 中国科学院上海微系统与信息技术研究所 | Data acquisition and dynamic topology control method based on SDMA (Space Division Multiple Access) in WSN (Wireless Sensor Network) |
| KR20120138341A (en) * | 2011-06-15 | 2012-12-26 | 주식회사 에스씨앤에스 | Ad-hoc communication system in the wireless network |
-
2013
- 2013-01-21 CN CN201310022128.3A patent/CN103068020B/en not_active Expired - Fee Related
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101778335A (en) * | 2009-01-14 | 2010-07-14 | 深圳市先进智能技术研究所 | Wearable monitoring system and method for community member monitoring |
| CN102098709A (en) * | 2010-11-04 | 2011-06-15 | 无锡泛联软件科技有限公司 | Gradient-based routing method in hybrid wireless sensor network |
| KR20120138341A (en) * | 2011-06-15 | 2012-12-26 | 주식회사 에스씨앤에스 | Ad-hoc communication system in the wireless network |
| CN102573023A (en) * | 2011-11-18 | 2012-07-11 | 中国科学院上海微系统与信息技术研究所 | Data acquisition and dynamic topology control method based on SDMA (Space Division Multiple Access) in WSN (Wireless Sensor Network) |
Non-Patent Citations (3)
| Title |
|---|
| Rounding via trees:deterministic approximation algorithms for group steiner trees and k-median;CHARIKAR,M.,CHEKURI,C.,GOEL,A.,ANDGUHA,S.;《In Proceedings of the thirtieth annual ACM symposium on Theory of computing(1998)》;19981231;全文 * |
| 一种基于移动无线传感器网络结构的数据采集协议;赵斌洁，陈光喜;《桂林电子科技大学学报》;20120831;第32卷(第4期);全文 * |
| 基于移动sink的无线传感器网络数据采集方案;郭剑 等;《通信学报》;20120930;第33卷(第9期);全文 * |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107295531A (en) * | 2017-07-25 | 2017-10-24 | 厦门理工学院 | A kind of wireless self-organization network covering method based on covering contribution |
| CN107295531B (en) * | 2017-07-25 | 2019-10-08 | 厦门理工学院 | A kind of wireless self-organization network covering method based on covering contribution |
Also Published As
| Publication number | Publication date |
|---|---|
| CN103068020A (en) | 2013-04-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Zaidan et al. | A survey on communication components for IoT-based technologies in smart homes | |
| Li et al. | Exploiting ubiquitous data collection for mobile users in wireless sensor networks | |
| CN103068020B (en) | The acquisition method of mobile data in wireless sensor network | |
| CN109313841B (en) | Method and system for implementing adaptive clustering in sensor networks | |
| Gutam et al. | Optimal rendezvous points selection and mobile sink trajectory construction for data collection in WSNs | |
| Wu et al. | Energy‐conserving data gathering by mobile mules in a spatially separated wireless sensor network | |
| Wang et al. | Sensor network navigation without locations | |
| Amiripalli et al. | Impact of trimet graph optimization topology on scalable networks | |
| KR101663994B1 (en) | METHOD FOR PROVIDING AN LIGHT-WEIGHT ROUTING PROTOCOL IN A IoT CAPABLE INFRA-LESS WIRELESS NETWORKS, RECORDING MEDIUM AND DEVICE FOR PERFORMING THE METHOD | |
| Wirawan et al. | Research in wireless sensor networks: optimization service discovery using attenuated bloom filter | |
| He et al. | Greedy construction of load‐balanced virtual backbones in wireless sensor networks | |
| Sadio et al. | Rethinking intelligent transportation systems with Internet of Vehicles: Proposition of sensing as a service model | |
| KR101616211B1 (en) | Scalable networked device dynamic mapping | |
| Liu et al. | Real-time search-driven caching for sensing data in vehicular networks | |
| Khan et al. | QPRD: QoS‐Aware Peering Routing Protocol for Delay‐Sensitive Data in Hospital Body Area Network | |
| JP5679768B2 (en) | Route control method, communication system, wireless terminal and gateway terminal | |
| CN111641969B (en) | Wireless multi-hop ad hoc network data distribution method and device based on edge calculation | |
| Senturk et al. | Mobile data collection in smart city applications: the impact of precedence-based route planning on data latency | |
| Julien et al. | Rethinking context for pervasive computing: Adaptive shared perspectives | |
| Asgarnezhad et al. | An effective combined method for data aggregation in WSNs | |
| Jing et al. | An energy-efficient routing strategy based on mobile agent for wireless sensor network | |
| KR100760947B1 (en) | Routing Protocol Provision in Wireless Sensor Network System | |
| JP2017139635A (en) | Route selection device and route selection method | |
| Ye et al. | Lifetime optimization by load-balanced and energy efficient tree in wireless sensor networks | |
| Choi et al. | Cost-effective monitoring algorithm for cyber-physical system platform using combined spatio-temporal model |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20161228 |
|
| CF01 | Termination of patent right due to non-payment of annual fee |