Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

3.3 AREA-DOMINATING SET BASED SENSOR AREA COVERAGE ALGORITHM

Sheu et al. (2007) proposed a localized protocol to find a set of connected sensor nodes to cover the required region in heterogeneous sensor networks. Sensor nodes may have different SR and CR. A sensor may need multiple hops to reach its sensing neighbors if SR > CR. This case is of theoretical interest only since in practice CR > SR. The protocol consists of three phases: neighbor discovery, self-pruning, and active sensing neighbors discovery.

Each sensor collects information on its sensing neighbors by “hello” messages (neighbor discovery). The node information includes a node's ID, sensing range, location, and priority. The priority could be residual energy, sensing range, or communication degree, or a combination of several metrics (priorities are assumed to be distinct among nodes). Note that flooding is required for a node to learn its sensing neighbors if SR > CR. Only this phase requires message exchanges among nodes. The remaining two are decisions made by each node without communicating with others.

In the self-pruning phase, each node determines whether or not to be active. It decides to be active if its sensing area is not completely covered by the union of sensing areas of its sensing neighbors that have higher priority than the node. After this phase, the required region is fully covered by the active sensing nodes.

In the active sensing neighbor discovery phase, each sensing node A determines active ...