Distributed Topology Control Based On Coalition Formation Game In Wireless

Abstract

It becomes possible to control topologies when network formations are viewed as a global cooperative game, such that mobile nodes get connected to form an enormous coalition. The coalition consumes a lot of power to sustain constant information exchange making the coalition unhelpful. Group rationalities are never satisfied, and the gains from group formations get reduced. The report focused on the development of topology controls acting in the form of cooperative paradigms using mobile nodes aimed at improving connectivity within networks. The topology control also ensures that information exchange power costs are reduced. The report proposed the development of an algorithm that is responsible for the development of coalitions, so the coalitions are formed using the algorithm using a merge-and-split rule. A coalition link maintenance is attained depending on the transferred marginal utility within the framework of the bargaining game. The simulation tests performed illustrated that the proposed distributed topology does not consume a lot of power, unlike the previous scenario. Information exchange within a distributed topology becomes relatively little and enjoys better connectivity because of the algorithm that performs maintenance, unlike the non-cooperative frameworks.

Keywords: link maintenance, topology control, bargaining game and coalition formation game.

Introduction

Topology control was meant for wireless sensor networks, wireless mesh networks and mobile ad hoc networks with the goal of improving the performance of the networks. Topology control is studied in cognitive radio MANETs, and it eliminates the interference caused to primary users, other than improving the availability of links. Topology controls in wireless networks include mobile nodes and links that connect the mobile nodes together.

Network topologies are created when mobile nodes link with their neighbors and related links leading to a dense network developed using maximum transmission power. Control topologies are developed with the notion of reducing the energy consumed while eradicating signal interference, thus improving network connectivity. Topology controls increase the overall network lifetime because unwanted links get eliminated.

A network topology becomes dynamic since links become developed or destroyed as necessary. Power transmission changes within nodes make it necessary to delink or create new nodes, thanks to network topology. Unreliable links have become a thing of the past in distributed topology networks, leaving the network efficient.

Distributed topology control invokes other mobile nodes in information exchange and making decisions and that consumes a lot of power. The report focuses on improving the connectivity within the network and the consumption of a small amount of power. Various methods apply in the implementation of topology control.

Mobile nodes create topology through network formation. Topologies might be created through game-theoretic approaches to develop networks in communication networks. Additional studies regarding non-cooperative network performance focus on various topology designs and considerations based on game theory.

Relay assignments in cooperative communications are classified as non-cooperative games. Potential games are classified as non-cooperative games and thus become applicable in the development of multi-domain wireless networks. MANETS, or wireless sensor networks, exhibit team spirit, which means they are classified as cooperative games. Wireless sensor networks might collaborate to ensure that data gets transmitted between nodes far apart.

Collaboration between mobile nodes becomes essential during the development of topology controls so that the network expands evenly and improves the connectivity within the network. A problem experienced in topology control arises when it becomes necessary to create a coalition between mobile nodes. Topology control is formed by considering a network like a global cooperative game, which allows mobile nodes to be connected into a grand coalition. Topology control must support the deletion or addition of nodes so that stability is attained within the network.

Topology control is known to generate high efficiency and performance improvement within a network. Topology control results in stability without wasting resources like power within a network. Grand coalitions do not add value because power consumption increases, and information exchange does not occur efficiently. Certain nodes in the grand coalition might separate and regroup to form their coalitions. It is not easy to identify a stable coalition within a network.

2.0 Game theory

Game theory focuses on mathematical models integrated to help study cooperation and conflict scenarios. Game theory allows individuals or teams to identify the most suitable action, which preempts the highest success level. The game becomes the study element in game theory, defining situations where:

• There are a minimum of two players: where a player could entail an individual, nation, company, biological species, or a wireless node in the scenario of a computer network.
• All players or participants have a minimum of given strategies at their disposal and the courses of action they could refer to.
• Strategies chosen by either partner implicate the end results of the game
• Numerical payoffs awarded to each successful player mark that their decisions differed from that of their choices.

John Nash, in 1950, identified that finite games portray strategic equilibrium (Nash equilibrium). Jandaeng, Suntiamontut, and Elz (2011) explained that a Nash equilibrium involves a sort of strategies implemented by each player, whose properties indicate that no single player might unilaterally alter their strategies and become competitively advantaged over their counterparts. Nash equilibrium augurs with non-cooperative game theory. Game theory got significant attention after 1994 when John Nash was awarded a Nobel Peace Prize.

2.1 Game theory terminologies

Terminologies linked with game theory are defined as follows:

Players: A player could be a person, team or nation making decisions in a game setting. A typical game involves two players. The players could involve two nations, A and B, that have the same goal to fight. Two or more contenders fight for a tender slot.

Strategy: A strategy defines the possible options that a player might execute within a game. A strategy involves a set of competing choices that one makes during a game. The strategy can be distinguished into either mixed or pure strategy.

Assuming that m defines the set of strategies that player A could make use of, while n indicates the strategies usable by player B. P_i indicates the probability of choosing the alternative player A, i=1, 2, 3, 4,…m. assume that q_j becomes the probability of choosing j for player B, for j=1, 2, 3, 4, ——n. The probability summation of the different alternatives of each player becomes

Pure strategy: a case when a player identifies a single strategy whose probability outcome is 1, then it is called pure strategy. The party or person identifies the strategy while ignoring other strategies. A player A that uses a single Pi value implies pure strategy, and the Pi value equates to 1. Thus, the remaining Pi values equate to 0. Probability samples obtained from a pure strategy could mean P₁=1, P₂=0, P₃=0 and so on. The summation of the probabilities generates 1, P₁+p₂+P₃+P₄=1+0+0+0=1.

Mixed strategy: A player that makes use of more than a single strategy follows a mixed strategy. The probability of relying on each strategy becomes less than 1, but their ultimate summation equals 1. Q1= 0, Q2=0.65 and Q3=0.35. From the scenario, the summation of the probabilities equals 1.

Q1+Q2+Q3= 0+0.35+0.65=1

Payoff matrix: A payoff refers to a number indicating the outcome that a player desires. For random outcomes, a player might weigh the outcome probabilities. The payoffs anticipated determine a player’s risk attitude. When a person really wants an outcome, then he or she increases their risk level towards those outcomes.

Nash equilibrium: Nash equilibrium is commonly known as strategies equilibrium. The Nash equilibrium involves a list of strategies, and one player is entitled to a single strategy. The players are limited to strategies such that they do not alter them unitarily since they would not attain a better payoff.

Perfect information: A game involves perfect information when, in all scenarios, a single player makes a move, and each one has information regarding the participation until the point where they play.

Dominating strategy: a strategy is described as a dominating strategy when it generates a better payoff to a player that uses the strategy not considering the actions of other players. A strategy weakly dominates others when it offers the least beneficial payoff.

Rationality: a rational player is a person who plays with the intention of maximizing their playoff. The rationality of participants entails common knowledge.

Strategic form, also referred to as normal form, allows the participants to determine their strategies simultaneously. The payoffs from the game are represented in a tabular structure alongside their respective strategy combination.

Zero-sum game: a game is deemed zero-sum when the summation of the payoffs becomes zero to all players. A zero-sum in the case of two players, when a player wins, the other automatically loses. The interests of players in a two-player zero-sum game cancel one another diametrically.

Two-person zero-sum game: Two players with a player’s success equals the loss of another player. Both players cannot win at the same time, while both cannot lose at the same time.

Maximum principle: The principal increases the maximum guarantee for a player to maximum level, let us say player A. the minimum gains for player A are first acquired before other participant B gets their gains. The Maximum value describes the maximum values belonging to the minimal gains. The strategies applied to get the maximum value are referred to as the maximin strategy.

Minimax principle: The principle reduces the loss potential associated with maximum losses. The maximum loss accumulates for all player B’s alternatives other than A. The minimum value of the maximum losses is referred to as the minimax value. The strategy applied in obtaining the minimax value is known as the minimax strategy.

Saddlepoint: Games whose minimax values correspond with the maximum values are referred to as saddle points. The cell that augurs with minimax values and maximum values are referred to as saddle points. A game is believed to have a pure strategy when it contains a saddle point.

Value of the game: For a game with a saddle point, the cell value at the saddle point indicates the value of the game.

2.2Wireless sensor network

The wireless sensor network forms part of emergent technology that positively impacts human life. Kim (2018) argued that wireless sensor networks contain several wireless sensor nodes whose functions include the collection, processing, and storage of environmental information and also engage in communication with neighboring nodes when the need arises. Wireless sensor nodes have a range of applications not limited to civil and military areas, including intrusion detection, target field imaging, security and tactical surveillance, weather monitoring, and disaster management. Wireless sensor networks also help in the detection of ambient scenarios, which include light, sound, movement, temperature and inventory management.

Wireless sensory networks involve a complete setup of a network implemented within a region, whereas the sensory nodes’ positions do not require them to become pre-determined or otherwise connected. Wireless sensory networks engage their data into electronic signals, processed and applied to detect signal characteristics of the places they occur. Wireless sensor networks become unique because of the cooperative feature of their sensor nodes. The wireless sensor networks could help rescue operators by assisting them in locating survivors, making the rescue team aware of the prevailing situation and identification of risky places in the disaster setting.

The sensor nodes communicate with one another directly or through an external Base Station (BS). It is possible to apply a large number of sensors to read signals from distant geographical regions with a high accuracy level. Wireless sensor nodes form a fundamental feature within wireless sensor networks. The diagram Figure 1 indicates a sensor node architecture. The sensor node architecture involves the sensors, processor, communication and power sub-systems. Additional components might become part of the sensor nodes, which include power generator and mobilizer location finding systems and others. Sensing units are composed of two subunits: Analog-to-Digital Converter (ADC) and sensors.

• Processing Unit
• Transceiver
• Processor
• Power Unit
• Memory
• I/O
• Sensors
• ADC

The ADC becomes responsible for converting the analog signals that the sensors generate to digital signals. Once the digital signals are generated, they get transmitted into the processing unit. The system does not interpret analog signals, which means they must be transformed into digital signals whose meaning the system readily interprets.

The processing units perform the duty of comprehending the digital signals into the required form that a human being might interpret. The processing unit choice determines the efficiency and flexibility attainable in terms of performance and energy. Processors come in various forms, not limited to digital signal processors, microcontrollers, application-specific circuits, digital signal processors and Field Programmable Gate Arrays. A transceiver unit contains a receiver and a transmitter, which receive and transmit signals within a network.

The power unit formulates an important sensor node and it may source its power from different power sources like a solar cell. Routing techniques, sensor networks, and sensing tasks would require an accurate knowledge of location. A sensor node, therefore, contains location-identifying systems in most cases (Zeng, 2015). A mobilization becomes essential when moving sensor nodes in order to conduct the intended tasks. The sub-units might have to fit inside a miniature module to deliver the intended tasks. The size of the subunits might become less than a cubic centimeter so that it gets easily suspended in the air.

Sensor nodes become scattered within a sensor field with the capabilities of collecting and routing data to the required sink. The process occurs through a multi-hop infrastructure indicated in the diagram below.

• Internet
• User (Task Manager)
• Base Station
• Event

The sink communicates to the users through the satellites or the internet. Figure 3.3 below illustrates the protocols that apply in the sensor nodes and the sink. Zeng (2015) argued that the network protocol illustrates routing awareness, power efficiency, network participation and data integration. The protocol layers include the transport layer, application layer, data link layer, network layer, and physical layer. Other layers include the task management plane and the mobility management plane.

Source:-

The physical layer handles the efficient modulation and simple modulation needs, sending and receiving techniques, alongside the frequency selection, signal detection, carrier frequency generation and data encryption. It is important to make a good choice of modulation scheme so that reliable communication becomes possible within the network.

The data link layer within the network protocol multiplexes data streams, detection of data frames, error controls and medium access. Medium Access Control functions to limit the possibility of collision with other broadcasts. The data link layer ensures that power efficiency gets well maintained and routes the data which the transport layer supplies. The network layer ensures power efficiency within the node alongside the data routes that the transport layer institutes. The transport layer maintains data flow when the network sensor requires that the data flow be maintained. The transport layer becomes helpful when the network gets accessed through an external network or through the internet.

The application layer might generate various application software that augurs with the tasks at hand. Power management planes monitor the power; mobility movement monitors the movement, and task management planes monitor the tasks distributed within the sensor nodes. The three planes allow the sensor nodes to coordinate tasks, thus reducing the power consumed.

2.3 Motivations

Wireless Sensor Networks have several areas of application not limited to environmental monitoring, military and health sectors. The popularity of wireless networks made the growth occur, and it is expected to occur in several other sectors. Energy constraint limits the applicability of Wireless Sensor Networks. Variations in energy levels reduce the network lifetime, and additional effort is needed to make its use efficient. The energy consumed within the network’s sensor nodes ought to be reduced.

Research conducted in Wireless Sensor Networks designed sensor network algorithms that consume little power. Other research focused on sensor node coverage areas, using localized k coverage and centralized algorithms. The algorithms indicated that a network gets reconfigured to reduce the energy wasted based on the network size. Game theory applications increased in wireless sensor network designs. The report applied the use of game theory for wireless sensor networks. Different research papers were published between 2003 and 2013 regarding the application of game theory for wireless sensor networks. Different game theory methodologies are applied in the development of wireless sensor networks.

Cooperative game theory studies a rational player’s behavior using analytical tools when the players cooperate, and the behaviors of all players are considered. Non-cooperative game theory heavily applies in wireless sensor networks. Non-cooperative game theory exhibits the purchase, sale or utilize goods by the nodes depending on the virtual market prices. Nodes maximize the profit potential by engaging in different actions. The profitability attained by a node depends on the action’s success. Non-cooperative game theory success depends on a single utility rather than the efforts of the entire network. Cooperative game theory might attain Pareto-optimal performance, thus raising the payoff within the network without utilizing excessive power and resources. Apart from non-cooperative and cooperative game theories, repeated game theory relates to dynamic games, whereby a game is played severally, and the participants view the previous outcomes before engaging the future games.

2.4 Game theory in wireless sensor networks

A typical game involves three components: players, payoffs and the strategies used by the players to succeed. Nodes or players make all decisions regarding the games. Nodes or players make use of strategies based on what they intend to achieve. Successful decisions result in payoffs for the players. Table 1 below indicates the wireless sensor networking game typical components.

Table 1: Wireless Sensor Networking Game Components

Different game theory models are applicable depending on factors at hand like the sum of gains or losses in the game, number of participants, strategies deployed, two two-player or multiple-player game. Game theory terminologies differ based on the factors at hand, so various terms apply to various situations. Table 2 illustrates the common game theory models that apply in wireless sensor networks and the associated terminologies.

Table 2. Game Theory Methods and Terminologies in Wireless Sensor Networks

The non-cooperative game theory relates to strategic choice analysis alongside explicit models, which a player in the game follows based on their interests. Non-cooperative games are differentiated into several other categories based on the game rules. Non-cooperative game theory is categorized into static or dynamic games, depending on whether the player makes simultaneous moves.

A static game theory requires the player to engage in simultaneous strategy decision-making and does not require the knowledge of other players. The person makes their simultaneous decisions in isolation without considering the choices elicited from the rest of the game players. It is possible to represent static games using a table, often known as strategic forms or normal forms.

The dynamic game requires the person to follow a strategic decision but in strict order. A player plays when their turns arrive, and they must understand or know in the least the moves their previous players made. Dynamic games are illustrated using extensive game forms, which indicate the list of actions that a person might implement as a player and their respective outcomes.

Irrespective of whether a player knows the payoff characteristics regarding their opponents, non-cooperative games fall into two classes: complete information games and incomplete information games. Complete information games require all participants to have full information regarding the strategy spaces, characteristics of other players and the payoff functions, but this does not matter in the case of incomplete information games. There are various categories of non-cooperative games and their equilibrium concepts.

Table 3.

Non-cooperative game theory applications within wireless networks

Non-cooperative game theory focuses on interaction strategies applied by players in a game. Players act as agents within a game and their goal aims at maximizing the utilities through identifying the most applicable strategy within the game. Utility functions apply non-cooperative game theories to identify the Nash equilibrium. Non-cooperative game theories apply in congestion controls, distributed resource allocation, and spectrum sharing.

4.0 Cooperative Game Theory

A cooperative game requires the participants to engage in commitments that bind them to the game. The players form a coalition and wealth distribution based on the payoff ratios. Two methods determine wealth distribution; for instance, they focus on measures that increase the reasonable terms that favor all participants within the game. They also engage in solutions that create stability for everyone in the game. Cooperative game theory applies in international relations and political science, where power could become a problem.

Cooperative game theory does not require a solution concept that applies throughout the game. Multiple solutions occur in a cooperative game theory so that inherent conflicts get resolved of what comes first and last. Non-cooperative fame focus on the rationality of individuals and optimal strategies the individuals make use. Cooperative game strategies focus on fairness, effectiveness and collective rationality so that all participants enjoy the payoffs while they also contribute.

5.0 Cooperative game theory applications in wireless networks

Nodes come together into a coalition with the intention of reducing energy consumption in wireless sensor networks and prolonging the lifetime of the networks. Coalitional game theory forms an important aspect of game theory, and the former sometimes denotes the latter. Players identify strategies that increase their utility after the coalitional game theory formation in a wireless sensor node. Coalition formation implemented through merger and split makes a perfect march. Permutations are performed whose outcomes assure the participants of the highest possible utility value.

Groups are organized with the intention of putting together sensor nodes so that they cooperate amongst themselves. The nodes do not control the grouping activities, and the group leaders have given nodes that contain information regarding new sensor nodes that become new group members. Wireless sensor nodes are classified into various categories, including:

• Sensor nodes that have the same data are categorized into a single group
• Sensor nodes that portend a relatively short distance between them fall into a single group

Coalition formation occurs in a generic approach that follows the merger and split mechanisms. Cooperative game theories break into two distinguished categories:

Transferable-utility game: – The measurement allocation payoff becomes transferable

Non-transferable-utility game: – The payoffs for each coalition member depend on their contribution level and the strategies which they follow.

Shapley’s value comes from cooperative game theory. Shapley values become an important concept in game theory, representing single-valued solutions within cooperative game theories. Shapley value becomes useful in game theory when one intends to allocate resources which the players would achieve when they come together.

Shapley value gets explained for both NTU a TU games to distinguish the conflict that players face. Cooperative game theory applies to creating algorithms of dynamic coalitions, which gives nodes the power to determine the coalitions that apply to them and join. Nodes make decisions on the appropriate groups, which will facilitate their performance while increasing their sleeping time.

6.0 Relevance of game theory to wireless networking and communication

Ad hoc networks have occupied a big position in networking and wireless communication for years. Ad hoc networks involve multi-hop networks that are configured on their own and lack a central point of authority. The ad hoc operations and configurational features get distributed properly since no central management point takes charge of managing the activities. Most of the nodes within an ad hoc network lack adequate power and energy. Emerging wireless network technologies like mesh networks, sensor networks, or pervasive computer systems focus on power energy awareness, operational decentralization, and self-configuration. Game theory facilitates the interaction of agents in an autonomous structure. Game theory becomes essential in wireless sensor networks because they encourage and support autonomy among the members of the network.

Nodes that run through a wireless sensory network engage in autonomous decision-making. However, the decisions might be made in regard to the algorithmic protocols and the network designs. Apart from the network protocols, the nodes must have the privilege to make decisions alone. Autonomous decisions performed by the nodes within the network include packet forwarding, power transmission, and back-off time. Certain nodes might operate for the greater good of the network. The nodes might make independent decisions that improve the overall network structure. In given scenarios, nodes take the role of acting selfishly and pursue their individual interests.

Nodes might also perform risky activities that intend to ruin the network protocols for other network users. In the previous scenarios, game theory becomes helpful in creating beneficial autonomy that takes into consideration all network participants. Game theory monitors the wireless sensory nodes so that conflicts amongst participants get eliminated, and alternatives are provided. Nodes or players are organized in a manner that they offer value to the network. Nodes might share objectives, but their perspectives on attaining the objectives differ. The game theory becomes helpful in making sure that the individual members help the group members align with the goals and objectives of a group within a network. Game theory eliminates the conflict potential in attaining the goals and objectives within a network.

7.0 Conclusion

Game theory allows players to make rational decisions while playing. Game theory has a wide application in sociology, conflict resolution, economics, politics, communication and computer networking. Game theory helps transfer data within networks where conflicts become persistent. The report identified a game model that interprets the working mechanism and sections that require studies. Game theory becomes an important research tool in implementing a successful wireless sensory network. Wireless network technology is being adopted in everyday technology, but it becomes more complex the bigger it becomes. It is not possible to describe the payoffs at any given time, but it is possible to put strategies that add value within a wireless network. It is not possible to identify the conflict areas when the network gets designed, but game theory offers potential options when the network becomes operational. Game theory models reveal important features that allow one to understand a complex network model and develop an insightful solution to the problem at hand. It is not possible to end all the network problems, but game theory provides achievable alternatives for resolving the network issues.

References:

Baranidharan, B. (2011). A New Graph Theory based Routing Protocol for Wireless Sensor Networks. International Journal On Applications Of Graph Theory In Wireless Ad Hoc Networks And Sensor Networks, 3(4), 15-26. http://dx.doi.org/10.5121/jgraphoc.2011.3402

Charilas, D., & Panagopoulos, A. (2014). A survey on game theory applications in wireless networks. Computer Networks, 54(18), 3421-3430. http://dx.doi.org/10.1016/j.comnet.2010.06.020

Chen, C. (2012). A Novel Range-Free Localization Scheme for Wireless Sensor Networks. International Journal On Applications Of Graph Theory In Wireless Ad Hoc Networks And Sensor Networks, 4(2), 1-13. http://dx.doi.org/10.5121/jgraphoc.2012.4201

Farzaneh, N., & Yaghmaee, M. (2014). An Adaptive Competitive Resource Control Protocol for Alleviating Congestion in Wireless Sensor Networks: An Evolutionary Game Theory Approach. Wireless Personal Communications, 82(1), 123-142. http://dx.doi.org/10.1007/s11277-014-2198-9

Jandaeng, Suntiamontut, & Elz. (2011). PSA: The Packet Scheduling Algorithm for Wireless Sensor Networks. International Journal On Applications Of Graph Theory In Wireless Ad Hoc Networks And Sensor Networks, 3(3), 1-12. http://dx.doi.org/10.5121/jgraphoc.2011.3301

Khanmirza, H., & Yazdani, N. (2015). Game of energy consumption balancing in heterogeneous sensor networks. Wireless Communications And Mobile Computing, 16(12), 1457-1477. http://dx.doi.org/10.1002/wcm.2606

Kim, S. (2018). A better-performing Q-learning game-theoretic distributed routing for underwater wireless sensor networks. International Journal Of Distributed Sensor Networks, 14(1), 155014771875472. http://dx.doi.org/10.1177/1550147718754728

Liu, Q., & Liu, M. (2017). Energy-efficient clustering algorithm based on game theory for wireless sensor networks. International Journal Of Distributed Sensor Networks, 13(11), 155014771774370. http://dx.doi.org/10.1177/1550147717743701

Liu, Q., Yang, S., Ji, L., & Zhang, L. (2016). Game-theory-based coordination in wireless sensor and actor networks. IET Wireless Sensor Systems, 6(5), 166-172. http://dx.doi.org/10.1049/iet-wss.2015.0084

Luo, W., Zhai, Y., & Lu, Q. (2011). Study on Wireless Multimedia Sensor Networks. Journal Of Electronics & Information Technology, 30(6), 1511-1516. http://dx.doi.org/10.3724/sp.j.1146.2007.00016

Mohammadi, S., & Jadidoleslamy, H. (2011). A Comparison of Link Layer Attacks on Wireless Sensor Networks. International Journal On Applications Of Graph Theory In Wireless Ad Hoc Networks And Sensor Networks, 3(1), 35-56. http://dx.doi.org/10.5121/jgraphhoc.2011.3103

Peng, H., & Ju, C. (2016). Game theory based distributed energy efficient access point selection for wireless sensor network. Wireless Networks, 24(2), 523-532. http://dx.doi.org/10.1007/s11276-016-1350-8

Shen, S., Yue, G., Cao, Q., & Yu, F. (2011). A Survey of Game Theory in Wireless Sensor Networks Security. Journal Of Networks, 6(3). http://dx.doi.org/10.4304/jnw.6.3.521-532

Wu, H., & Bi, S. (2011). A Game Theory-Based Obstacle Avoidance Routing Protocol for Wireless Sensor Networks. Sensors, 11(12), 9327-9343. http://dx.doi.org/10.3390/s111009327

Zeng, J. (2015). Game Theory-based Energy Balance Routing with Incomplete Information in Wireless Sensor Networks. Acta Automatica Sinica, 34(3), 317-322. http://dx.doi.org/10.3724/sp.j.1004.2008.00317