Dynamic distributed clustering in wireless sensor networks via Voronoi tessellation control

ABSTRACT

This paper presents two dynamic and distributed clustering algorithms for Wireless Sensor Networks (WSNs). Clustering approaches are used in WSNs to improve the network lifetime and scalability by balancing the workload among the clusters. Each cluster is managed by a cluster head (CH) node. The first algorithm requires the CH nodes to be mobile: by dynamically varying the CH node positions, the algorithm is proved to converge to a specific partition of the mission area, the generalised Voronoi tessellation, in which the loads of the CH nodes are balanced. Conversely, if the CH nodes are fixed, a weighted Voronoi clustering approach is proposed with the same load-balancing objective: a reinforcement learning approach is used to dynamically vary the mission space partition by controlling the weights of the Voronoi regions. Numerical simulations are provided to validate the approaches.

KEYWORDS:

• Voronoi partitioning
• wireless sensor networks
• Markov decision processes
• reinforcement learning

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. I.e., there is a bounded and convex subset $\mathcal{Q}\subseteq \mathcal{A}$ s.t. ϕ( p ) > 0 if $\mathit{p}\in \mathcal{Q}$, and ϕ( p ) = 0 if $\mathit{p}\in \mathcal{A}\setminus \mathcal{Q}$.

2. Policies in which one action per state is chosen with probability 1 are called deterministic policies. Considering deterministic policies only is not a limitation in unconstrained MDPs, since a deterministic optimal policy always exists (Sutton & Barto, 1998).

3. Multisets, also commonly known as bags, are unordered collections of items which may contain duplicates. For example, the multiset {1, 1, 1, 2, 3} is equivalent to the multiset {1, 2, 1, 1, 3}, but differs from the multiset (also a set in this case) {1, 2, 3} because of the multiplicity of element 1. The multiset A = A ₁⊎A ₂ by definition contains only the elements that occur either in A ₁ or in A ₂, and the multiplicity of each element in A is the multiplicity of that element in A ₁ plus the multiplicity of that element in A ₂, e.g. {1, 1, 1, 2, 3}⊎{1, 2, 3} = {1, 1, 1, 2, 3, 1, 2, 3}.

Additional information

Funding

This work is partly supported by the European FP7 project SWIPE (Space WIreless sensor networks for Planetary Exploration) [grant number 312826].