Optimal vs rotation heuristics in the role of cluster-head for routing in IoT constrained devices

Wireless Sensor Networks (WSNs) are crucial for implementing the Internet of Things (IoT) vision. A WSN can include distributed devices that can be battery powered, have a small amount of memory, have limited CPU processing capabilities and limited transmission range. WSNs are categorised into two main types that are homogeneous and heterogeneous. Homogeneous WSNs are composed of nodes that are all equal while heterogeneous ones are composed of nodes that can have different transmission rate and different initial energy. Collecting data in an energy efficient manner is one of the main goals when building wireless sensor networks since devices are battery powered and battery replacement can be difficult or impossible to be performed. Clustering protocols are one of the main approaches that have been used in order to collect data in an energy efficient way. A clustering protocol groups nodes into a set of clusters. Each cluster has a representative node that is referred to as Cluster Head (CH). This collects data from its cluster members and forwards them to an external Base Station, possibly in a multi-hop way among cluster heads. A rotation strategy for electing the cluster head is often used together with clustering in order to prolong the network lifetime. Rotation eliminates the overhead traffic that is needed for leader election and cluster formation since the old cluster heads directly designate new ones. In this work, we describe an Optimum Rotation Scheduling (ORS) that uses Integer Linear Programming in order to find the optimum rotation strategy. ORS assumes the WSN clusters are already formed by using some clustering protocol. A novel integer linear programming formulation is then used in order to define a cluster head rotation that produces the optimum cluster lifetime. Comparisons with existing heuristics and the provided optimum are then shown and discussed by means of extended simulations involving both homogeneous and heterogeneous WSNs.