An Evolutionary Cluster-Game Approach for Wsns in Non-Collaborative Settings
No Thumbnail Available
Date
2018-12-05
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
In the designing of Wireless Sensor Networks (WSNs), it is often assumed that each sensor node faithfully follows the prescribed conventional standards without any deviation. Nevertheless, when WSNs that are located in the same vicinity are owned and managed by different network authorities, individual nodes will likely do what is most beneficial to its governing authority. As such a node may be reluctant to forward the packets of other authority‟s nodes, so as to preserve its resources (for instance, energy and CPU time).
Sensor nodes are small in size and have a very limited amount of energy which considerably limits the lifetime of WSNs if their resources could not be properly utilized. Cluster-based routing algorithms preserve energy by grouping nodes into multiple clusters. Moreover, it selects a single node in each cluster as the Cluster Head (CH) to communicate with a Base Station (BS) on behalf of other nodes. In an ideal collaborative setting, nodes should alternate the role of CH according to some fairness rule. However, in reality, a selfish (non-cooperative) node might refuse to volunteer: cooperation is not guaranteed in Multi-class WSNs (MWSNs). The degree of compliance of nodes to this fairness rule can greatly influence the Quality of Service (QoS) provided by the network. Consequently, the first and foremost step to address such a problem consists of building a model that captures and mitigates the essential aspects of an existing physical phenomenon, and then, designing an energy-efficient routing algorithm.
In this dissertation, we developed a model of an Evolutionary Collaborative Game (ECG): an evolutionary dynamics whereby players (i.e., sensor nodes) interact by adopting either cooperative or non-cooperative strategy and, then, evaluating their packet forwarding benefits. An analytic model of nodes‟ population evolution, called replicator dynamics is also systematically derived as a guide in the choice of the mechanisms. Nodes adapt their strategies on the basis of the outcomes of the interactions with other nodes and converge to an ESS. This corresponds to the anticipated behavioral outcomes in the dynamics whereby the population of nodes reaches a stable equilibrium.
Considering the ESS outcome that has been a desirable state of the system, we propose two algorithms for WSNs in non-collaborative settings. The first algorithm consists of cluster-based Collaborative Packets Forwarding (CPF), where nodes in the population game interact (i.e., each node interacts to any others) with the same probability. By introducing a rewarding
mechanism (also known as an incentive), it has been observed that nodes evolve and reach a collaborative stable equilibrium as per our conducted analysis that has been shown both analytically - in a stylized scenario, and numerically - by using simulations, (assuming the relations between payoff parameters (cost-to-benefit ratio (w) and reward-to-benefit ratio (d)) and the number of nodes (N)). Given the value of d is constant, it is observed that the quantified equilibrium decreases when the values of w and N increase, but when the value of d decreases the equilibrium drops more rapidly as a large number of nodes switch into non-collaborative behavior in order to conserve their resources.
Then, the achievements of collaborative equilibrium and cooperative-rate have been evaluated in the development of CH-determination of CPF algorithm. As such, CH role is determined and rotated based on the potential collaborations that the individual nodes made. The studied simulation results have revealed that CPF will be able to conserve the remaining energy of networks when comparing it with default case (i.e., Non-collaborative Packets Forwarding (NcPF) algorithm).
An algorithm called GREET (evolutionary Game theoRy based Energy EfficienT cluster-head determination algorithm) has also been proposed by assuming that nodes only interact with their neighboring nodes. In the evolutionary cluster-game, it is observed that the stable equilibrium has been reached without the requirement of any external enforcement mechanism. The probability of volunteering as CH candidate decreases with the growth of w and M (number of nodes in the given cluster). In the achievement of equilibrium probability, CH-enabled nodes start to decide whether to be a candidate CH or not in the current round. Then, considering the energy level of currently contested candidates (in case they are more than two), appointed-CH would be determined to represent its members in transmitting packets. Moreover, nodes with minimum residual energy will stay in CH-disallowed state until their energy level is on equal footing with others. This process, in turn, helps the algorithm to balance the energy consumption of nodes.
Subsequently, simulation results for both CPF and GREET were analyzed and compared with respect to other standard WSN algorithms such as LEACH and CROSS. It is found that GREET outperforms all of them in terms of network lifetimes and packet throughputs. The reason is that the achievement of nodes‟ collaborative equilibriums is balanced as well as the
role of CH is uniformly distributed and fairly rotated in extending energy utilizations. Although global information is required both in CPF and CROSS, CPF performs better than CROSS for certain payoff functions.
Description
Keywords
Cluster-Based Cpf Algorithm, Energy Efficient Algorithm, Evolutionary Cluster-Game, Evolutionary Collaborative-Game, Greet, Mwsns, Network Lifetime, Non-Collaborative Nodes