Architectures And Methods For Energy-efficient Querying And Indexing In Wireless Sensor Networks
Abstract
Wireless sensor networks have been an active research area for about
a decade due to their adaptability to applications involving
long-term environmental monitoring. Recent technologies make it
possible that a small device equipped with multi-purposed sensors,
small CPU and memory, wireless transmitter and receiver, and
software can form a network, measure some quantitative phenomena and
communicate with each other seamlessly. In wireless sensor networks,
one of the basic applications is to monitor events and measure
values at places that people cannot reach easily or where a long
term sensing task is required. In this case, we need to know the
properties of diverse types of sensor network queries and data that
are different from traditional ones. Also, we need to solve the
intrinsic sensor network problem, energy saving, since users want to
gather data for a long term and it is generally not feasible to
replace batteries in sensor devices after the sensors are deployed.
In order to solve this problem, first, we classify sensor network
queries and find a suitable network system that includes different
routing and storage types for each type of query. Second, energy
efficient indexing and data gathering methods for sensor networks
are studied. In energy efficient indexing, we propose a sectioned
tree index, which divides the network area into several squares and
each square has a local index subtree organized within that square.
Local trees are interconnected to form one big tree in the network.
Local trees are also built based on any algorithm that is energy
consumption aware at each sub-root node in a locally centralized
way. In energy efficient data gathering, we create energy-efficient
data gathering routing tree when we consider two-way communication
for reliable transmission and collision prevention. This makes the
problem intractable, and we prove our problem is NP-complete by
showing that a known NP-complete problem is a special case of our
problem. In order to get an energy-efficient routing tree, we
propose several heuristic techniques that backtrack one or two steps
(BT1 and BT2). We give various values as parameters in measuring
energy equation and simulate our proposed algorithms in diverse
conditions.