Much research has been done on wireless sensor networks. However, most protocols
and algorithms for such networks are based on the ideal model Unit Disk Graph
(UDG) model or do not assume any model. Furthermore, many results assume the
knowledge of location information of the network. In practice, sensor networks often
deviate from the UDG model significantly. It is not uncommon to observe stable long
links that are more than five times longer than unstable short links in real wireless
networks. A more general network model, the quasi unit-disk graph (quasi-UDG)
model, captures much better the characteristics of wireless networks. However, the
understanding of the properties of general quasi-UDGs has been very limited, which
is impeding the design of key network protocols and algorithms.
In this dissertation we study the properties for general wireless sensor networks
and develop new topological/geometrical techniques for wireless sensor networking.
We assume neither the ideal UDG model nor the location information of the nodes.
Instead we work on the more general quasi-UDG model and focus on figuring out
the relationship between the geometrical properties and the topological properties of
wireless sensor networks. Based on such relationships we develop algorithms that can
compute useful substructures (planar subnetworks, boundaries, etc.). We also present direct applications of the properties and substructures we constructed including routing,
data storage, topology discovery, etc.
We prove that wireless networks based on quasi-UDG model exhibit nice properties
like separabilities, existences of constant stretch backbones, etc. We develop
efficient algorithms that can obtain relatively dense planar subnetworks for wireless
sensor networks. We also present efficient routing protocols and balanced data storage
scheme that supports ranged queries.
We present algorithmic results that can also be applied to other fields (e.g., information
management). Based on divide and conquer and improved color coding
technique, we develop algorithms for path, matching and packing problem that significantly
improve previous best algorithms. We prove that it is unlikely for certain
problems in operation science and information management to have any relatively
effective algorithm or approximation algorithm for them.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/86012 |
| Date | 10 October 2008 |
| Creators | Zhang, Fenghui |
| Contributors | Chen, Jianer, Jiang, Anxiao (Andrew) |
| Publisher | Texas A&M University |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation, text |
| Format | electronic, born digital |
Page generated in 0.0017 seconds