CN105282759A - Three dimensional sensor network surface skeleton extraction method - Google Patents
Three dimensional sensor network surface skeleton extraction method Download PDFInfo
- Publication number
- CN105282759A CN105282759A CN201510791389.0A CN201510791389A CN105282759A CN 105282759 A CN105282759 A CN 105282759A CN 201510791389 A CN201510791389 A CN 201510791389A CN 105282759 A CN105282759 A CN 105282759A
- Authority
- CN
- China
- Prior art keywords
- node
- boundary
- point
- inundation
- 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.)
- Pending
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W16/00—Network planning, e.g. coverage or traffic planning tools; Network deployment, e.g. resource partitioning or cells structures
- H04W16/24—Cell structures
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W24/00—Supervisory, monitoring or testing arrangements
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W84/00—Network topologies
- H04W84/18—Self-organising networks, e.g. ad-hoc networks or sensor networks
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Image Analysis (AREA)
Abstract
The invention discloses a three dimensional sensor network surface skeleton extraction method. The three dimensional sensor network surface skeleton extraction method includes the steps: every internal node calculates the feature point thereof; a restrictive broadcast mode is used to enable the feature points of the nodes to form a plurality of feature connected components; surface skeleton points are identified; a maximum independent set of the surface skeleton points is constructed; the surface skeleton nodes in the maximum independent set are used to obtain a Voronoi graph; and based on the Voronoi graph, triangularization of the dual graph Delaunay can be obtained so as to obtain a three dimensional sensor network surface skeleton. The surface skeleton point identifying method has no use for depending on a special grid structure and cannot be influenced by network noise, distance round-off error and sparse network, and can obtain a steady surface skeleton.
Description
Technical field
The invention belongs to wireless sensor network technology field, more specifically, relate to a kind of three-dimension sensor network face framework extraction method.
Background technology
Facial bone frame is the important framework of three-dimension sensor network, fully can reflect its geometry topological characteristic; There are some researches show, utilize the geometry topological characteristic of sensor network, contribute to designing high performance procotol.In computer vision research field, the research about three-dimensional body facial bone frame emerges in an endless stream, but mostly concentrates on continuous domain, and adopts centralized algorithm to carry out, and thus can not be applied directly to and have in the discrete sensor network of resource constraint feature.The existing document extracted about sensor network skeleton, mainly concentrates on two-dimension sensors network, and the face framework extraction method that XiaSu etc. propose is then the unique achievement in research in three-dimension sensor network.Its specific practice is: first set up a unit tetrahedral element (UnitTetrahedronCell, UTC) network configuration, then in a recursive manner from every one deck of " strip off " UTC network configuration while of inner and outer boundary, until can strip off without any layer, namely obtain network facial bone frame.But this method similar based on morpho logical thinning, that propose with Blum in essence burning grass model, very responsive and usually cannot accurate locating surface skeleton point to used distance metric.In addition, it is very easy to affect by noise at the boundary, and then produces bandage skeleton, must adopt optimization process afterwards.What is more important, the method depends on the UTC network configuration of foundation, and set up UTC structure and usually need network density larger, comparatively sparse at network, exist small size cavity and only have link information between node (but not node coordinate information) available time, UTC result accurately be obtained very difficult.Finally, because UTC structure needs to build in advance, the method can not be applied in dynamic network.When network topology adds because of node failure or new node and changes, rebuild UTC and can bring huge communication overhead.
Summary of the invention
For existing methodical deficiency, the present invention proposes a kind of three-dimension sensor network face framework extraction method, the method can not be subject to the impact of the factors such as the sparse and distance rounding error of boundary perturbation, network density, can obtain more real network topology structure.
A kind of three-dimension sensor network face framework extraction method, comprises the following steps:
(1) each internal node calculates its characteristic point, if the jumping figure of the nearest boundary point of certain internal node is k, then the boundary point of jumping apart from this internal node k+1 is also seen as characteristic point; Be called extension feature point;
(2) adopt restricted broadcast mode, the characteristic point of node is formed multiple feature connected component, and on border, carry out the geodesic distance that hop-by-hop expansion comes between calculated characteristics connected component;
(3) feature connected component geodesic distance being less than ε is merged into large ε connected component.If ε connected component number is more than or equal to 2, then respective inner node is facial bone frame point; Otherwise it is not just facial bone frame point;
As innovation of the present invention, propose first and utilize geodetic ε equivalence relation to extract sane facial bone frame.If the geodesic distance of two nodes (or UNICOM is separated) between a, b is less than given arithmetic number ε, then them are claimed to be geodetic ε equivalences.This skeleton node recognition method based on geodetic ε equivalence relation, have robustness, and it is that in continuous domain, facial bone frame is defined in the popularization in discrete sensor network for factors such as noise at the boundary, node failure and network low-densities.
(4) construct the maximal independent set of facial bone frame point, make the jumping figure distance wherein arbitrarily between the skeleton point of two sides be greater than 1 and be less than or equal to 3; In the maximal independent set obtained like this, the distribution of facial bone frame point is relatively uniform, can better reflect network geometric topology feature.
(5) utilize the facial bone frame node in maximal independent set, obtain Voronoi figure, wherein each Voronoi unit has and only has a facial bone frame point.Scheme based on this Voronoi, utilize existing method to obtain its dual graph Delaunay trigonometric ratio, thus obtain three-dimension sensor network facial bone frame.
Technique effect of the present invention is embodied in:
The present invention obtains ε connected component by introducing parameter ε, and identify facial bone frame point based on ε connected component, it is based on defining the facial bone shelf collection identified in continuous domain, its advantage is the harmful effect that this recognition methods can be avoided the factors such as rounding error, noise at the boundary and network low-density and causes more to be adapted to discrete three-dimension sensor network.Simultaneously, traditional centralized facial bone frame extraction algorithm is also not suitable for the such distributed network of sensor network, and sensor node has the finiteness feature of energy and computing capability etc., a distributed approximation method should be designed, while basic reservation centralized algorithm superiority, maintain distributed nature.Because the present invention is distributed algorithm, be applicable to being applied in and have in the three-dimension sensor network of distributed nature; Time, the space complexity of this algorithm are all linear with network size, are with good expansibility, and can be applied in extensive three-dimension sensor network; Compared with algorithm in the past, it does not rely on any special construction, and the control of the factor such as boundary noise, network are sparse and network is sparse is more flexible, can extract more sane network facial bone frame.
Accompanying drawing explanation
Fig. 1 is the inventive method schematic flow sheet;
Fig. 2 is three-dimension sensor network model example figure of the present invention;
Fig. 3 is the feature connected component schematic diagram of three-dimension sensor network facial bone frame node of the present invention;
Fig. 4 is the feature connected component schematic diagram of three-dimension sensor network non-face skeleton node of the present invention;
Fig. 5 is the facial bone frame node schematic diagram identified in three-dimension sensor network of the present invention;
Fig. 6 is very big independent face skeleton point set schematic diagram in three-dimension sensor network of the present invention;
Fig. 7 is three-dimension sensor network facial bone frame schematic diagram of the present invention.
Embodiment
In order to make object of the present invention, technical scheme and advantage clearly understand, below in conjunction with drawings and Examples, the present invention is further elaborated.Should be appreciated that specific embodiment described herein only in order to explain the present invention, be not intended to limit the present invention.In addition, if below in described each execution mode of the present invention involved technical characteristic do not form conflict each other and just can mutually combine.
The sensor network that the present invention applies with only the link information between transducer, and we utilize the method in existing document to identify network boundary, therefore can suppose that the boundary information of sensor network is known.
Fig. 1 is the inventive method schematic flow sheet, comprises the following steps:
Step 1. recognition feature point
Each boundary node initiates inundation in network internal with roughly the same time, inundation information comprise boundary node ID and for reflect inundation information process jumping figure distance, be initialized as 0 counter.After receiving the inundation information from certain boundary node (such as boundary point q), node p performs following strategy:
If do not receive the inundation information from other boundary nodes before node p, then boundary point q and two internodal jumping figure distances are saved in its nearest boundary point list List (p) by p, and counter are added the inundation information that forwards after 1 and upgrade to its neighbor node;
Otherwise, if the distance of p to q (can be reflected by counter) is less than or equal to 1 with the difference of the minimum value of boundary node distance in p to List (p), then boundary point q and two internodal jumping figure distances are saved in its nearest boundary point list List (p) by p equally, then counter are added the inundation information of forwarding renewal after 1 to its neighbor node; Otherwise the inundation information received directly abandons by p.
In this way, each node can record its extension feature node, and with these internodal jumping figure distances.
Fig. 2 is the three-dimension sensor network schematic diagram of example application.
Step 2. identifies skeleton node
These (expansion) characteristic nodes initiate restricted inundation on network boundary, to set up the connected component that several are made up of enlarging property node.Then, given system parameters ε, the boundary node in each connected component is endowed identical but unique identifier, then these boundary points initiate inundation, inundation information comprises the identifier sum counter of boundary point, be used for reflecting inundation information the jumping figure of process, be initialized as 0.When after the information that boundary point p receives from boundary point q, perform following strategy:
If node p does not also have identifier, then the identifier of oneself is set as the identifier identical with q by it, is transmitted to neighbours' boundary node after counter is added 1;
Otherwise if node p and q has different identifiers, and their counter sum is less than ε, then node p is transmitted to neighbours' boundary node after counter is added 1;
Otherwise the inundation information received directly abandons by p.
In this way, in network boundary, set up the communications cost that ε connected component consumes will be very low.According to ε connected component number, each node can judge whether himself is facial bone frame point.That is, if ε connected component number is more than or equal to 2, then this node is facial bone frame point, otherwise it is non-skeleton point.
Fig. 3 is the feature connected component schematic diagram of three-dimension sensor network facial bone frame node of the present invention;
Fig. 4 is the feature connected component schematic diagram of three-dimension sensor network non-face skeleton node of the present invention;
Fig. 5 is all facial bone frame node schematic diagrames identified in three-dimension sensor network of the present invention.
Step 3. is independent face skeleton point set structure greatly
In order to avoid the harmful effect that the factor such as rounding error, noise at the boundary is brought, the identification of facial bone frame point is based on extension feature node, and the characteristic node of non-critical, the facial bone frame point identified although it is so is all similar to and is in network center, its drawback is that the facial bone frame point identified may be more, especially, in the network with parallel boundary, this sets up to facial bone frame and brings certain trouble.For head it off, we construct maximal independent set in these facial bone frame nodes identified, and then carry out trigonometric ratio to facial bone frame point wherein, obtain final facial bone frame.Because facial bone frame is also two-dimentional flow pattern, the algorithm calculating maximal independent set in two-dimension sensors network also can use, therefore, utilize the method in existing document can construct the maximal independent set of facial bone frame point, the jumping figure distance wherein between any two points is greater than 1 and is less than 3.
Fig. 6 is example of the present invention three-dimension sensor network very big independent face skeleton point set schematic diagram used.
Step 4. matsurface skeleton is set up
Utilize the facial bone frame node in maximal independent set, can obtain Voronoi figure, wherein each Voronoi unit has and only has a facial bone frame point in maximal independent set.Scheme based on this Voronoi, the facial bone frame point in adjacent Voronoi unit can couple together by we, obtains its dual graph Delaunay trigonometric ratio, thus generating network matsurface skeleton.
Fig. 7 is the matsurface skeleton of the three-dimension sensor network of example of the present invention.
Those skilled in the art will readily understand; the foregoing is only preferred embodiment of the present invention; not in order to limit the present invention, all any amendments done within the spirit and principles in the present invention, equivalent replacement and improvement etc., all should be included within protection scope of the present invention.
Claims (3)
1. a three-dimension sensor network face framework extraction method, is characterized in that, comprises the following steps:
(1) each internal node calculates its characteristic point, if the jumping figure of the nearest boundary point of certain internal node is k, then the boundary point of jumping apart from this internal node k+1 is also seen as characteristic point;
(2) adopt restricted broadcast mode, the characteristic point of node is formed multiple feature connected component, and on border, carry out the geodesic distance that hop-by-hop expansion comes between calculated characteristics connected component;
(3) feature connected component geodesic distance being less than ε is merged into large ε connected component; If ε connected component number is more than or equal to 2, then respective inner node is facial bone frame point; Otherwise it is not just facial bone frame point;
(4) construct the maximal independent set of facial bone frame point, make the jumping figure distance wherein arbitrarily between the skeleton point of two sides be greater than 1 and be less than or equal to 3; In the maximal independent set obtained like this, the distribution of facial bone frame point is relatively uniform, can better reflect network geometric topology feature;
(5) utilize the facial bone frame node in maximal independent set, obtain Voronoi figure, wherein each Voronoi unit has and only has a facial bone frame point; Scheme based on this Voronoi, obtain its dual graph Delaunay trigonometric ratio, thus obtain three-dimension sensor network facial bone frame.
2. three-dimension sensor network face according to claim 1 framework extraction method, is characterized in that, described step (1) is specially:
Each boundary node initiates inundation in network internal with roughly the same time, inundation information comprise boundary node ID and for reflect inundation information process jumping figure distance, be initialized as 0 counter; After receiving the inundation information from certain boundary node, node p performs following strategy:
If do not receive the inundation information from other boundary nodes before node p, then boundary point q and two internodal jumping figure distances are saved in its nearest boundary point list List (p) by p, and counter are added the inundation information that forwards after 1 and upgrade to its neighbor node;
Otherwise, if the difference of the minimum value of the distance of p to q and the middle boundary node distance of p to List (p) is less than or equal to 1, then boundary point q and two internodal jumping figure distances are saved in its nearest boundary point list List (p) by p equally, then counter are added the inundation information of forwarding renewal after 1 to its neighbor node; Otherwise the inundation information received directly abandons by p;
In this way, its extension feature node of each nodes records, and with these internodal jumping figure distances.
3. three-dimension sensor network face according to claim 1 and 2 framework extraction method, is characterized in that, described step (2) is specially:
These characteristic nodes initiate restricted inundation on network boundary, to set up the connected component that several are made up of enlarging property node; Given system parameters, boundary node in each connected component is endowed identical but unique identifier, and then these boundary points initiate inundation, and inundation information comprises the identifier sum counter of boundary point, be used for reflecting inundation information the jumping figure of process, be initialized as 0.When after the information that boundary point p receives from boundary point q, perform following strategy:
If node p does not also have identifier, then the identifier of oneself is set as the identifier identical with q by it, is transmitted to neighbours' boundary node after counter is added 1;
Otherwise if node p and q has different identifiers, and their counter sum is less than ε, then node p is transmitted to neighbours' boundary node after counter is added 1; Otherwise the inundation information received directly abandons by p.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510791389.0A CN105282759A (en) | 2015-11-17 | 2015-11-17 | Three dimensional sensor network surface skeleton extraction method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510791389.0A CN105282759A (en) | 2015-11-17 | 2015-11-17 | Three dimensional sensor network surface skeleton extraction method |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN105282759A true CN105282759A (en) | 2016-01-27 |
Family
ID=55150913
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201510791389.0A Pending CN105282759A (en) | 2015-11-17 | 2015-11-17 | Three dimensional sensor network surface skeleton extraction method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN105282759A (en) |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20030112704A1 (en) * | 2001-12-14 | 2003-06-19 | Goff Douglas Francis | Process for interpreting faults from a fault-enhanced 3-dimensional seismic attribute volume |
| CN101505487A (en) * | 2009-02-27 | 2009-08-12 | 华中科技大学 | Sensor network skeleton extraction method |
| CN103400372A (en) * | 2013-07-10 | 2013-11-20 | 中国科学技术大学 | Three-dimensional topological information extraction method based on Reeb graph description |
| CN104202816A (en) * | 2014-08-22 | 2014-12-10 | 西北大学 | Large scale three dimension (3D) wireless sensor network node location method based on convex partition |
-
2015
- 2015-11-17 CN CN201510791389.0A patent/CN105282759A/en active Pending
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20030112704A1 (en) * | 2001-12-14 | 2003-06-19 | Goff Douglas Francis | Process for interpreting faults from a fault-enhanced 3-dimensional seismic attribute volume |
| CN101505487A (en) * | 2009-02-27 | 2009-08-12 | 华中科技大学 | Sensor network skeleton extraction method |
| CN103400372A (en) * | 2013-07-10 | 2013-11-20 | 中国科学技术大学 | Three-dimensional topological information extraction method based on Reeb graph description |
| CN104202816A (en) * | 2014-08-22 | 2014-12-10 | 西北大学 | Large scale three dimension (3D) wireless sensor network node location method based on convex partition |
Non-Patent Citations (1)
| Title |
|---|
| 刘文平: "《传感器网络的计算几何方法》", 30 September 2015 * |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Wang et al. | Boundary recognition in sensor networks by topological methods | |
| Liu et al. | On coverage of wireless sensor networks for rolling terrains | |
| CN110579214B (en) | Unmanned aerial vehicle path planning method and device | |
| CN107396374B (en) | Covering method based on virtual force and Thiessen polygon | |
| US20050288888A1 (en) | Semi-definite programming method for ad hoc network node localization | |
| CN101025831A (en) | Rapid precise constructing and shaping method for complex curved face product | |
| Risteska Stojkoska | Nodes localization in 3D wireless sensor networks based on multidimensional scaling algorithm | |
| CN102665253B (en) | Event detection method on basis of wireless sensor network | |
| Stojkoska et al. | Improved MDS-based algorithm for nodes localization in wireless sensor networks | |
| CN104902565A (en) | Distributed wireless sensor network three-dimensional multi-dimensional scaling (MDS) location method | |
| Fan et al. | DisLoc: A convex partitioning based approach for distributed 3-D localization in wireless sensor networks | |
| John et al. | Energy saving cluster head selection in wireless sensor networks for internet of things applications | |
| Sedighian Kashi | Area coverage of heterogeneous wireless sensor networks in support of Internet of Things demands | |
| Gupta et al. | An improved DV-maxHop localization algorithm for wireless sensor networks | |
| Li et al. | R3MR: Region growing based 3D mesh reconstruction for big data platform | |
| Das et al. | CHPT: an improved coverage-hole patching technique based on tree-center in wireless sensor networks | |
| Stojkoska | A taxonomy of localization techniques based on multidimensional scaling | |
| CN112702761B (en) | Method and system for detecting coverage hole of wireless sensor network | |
| CN105282759A (en) | Three dimensional sensor network surface skeleton extraction method | |
| CN109548138B (en) | Tracking area list management method based on overlapping community detection in small cellular network | |
| Almeida et al. | Fractal Clustering and similarity measure: Two new approaches for reducing energy consumption in Wireless Sensor Networks | |
| Wei et al. | BBIL: A bounding-based iterative method for IoT to localize things | |
| CN104765820A (en) | Non-invasive service dependency finding method | |
| Jiang et al. | Connectivity-based boundary extractionof large-scale 3D sensor networks: Algorithm and applications | |
| Wang et al. | SLICE: Enabling greedy routing in high genus 3-D WSNs with general topologies |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WD01 | Invention patent application deemed withdrawn after publication | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20160127 |