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 the connectivity within networks. The topology control also ensures that information exchange power costs reduce. 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 gets 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 a 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.
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 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 the network connectivity. Topology controls increases 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 makes it necessary to delink or create new nodes, thanks to network topology. Unreliable links 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 consumption of little 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 networks 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 classify as non-cooperative games, thus becomes 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 becomes when it becomes necessary to create a coalition between mobile nodes. Topology control gets formed through considering a network like a global cooperative game, which allows mobile nodes 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 into 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.
Game theory focuses on mathematical models, integrated to help study cooperation and conflict scenarios. Game theory allows individuals or teams 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.
- Strategies chosen by either partners implicates the end results of the game
- Numerical payoffs awarded to each successful player marks 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 than their counterparts. Nash equilibrium augurs with non-cooperative game theory. Game theory got a significant attention after 1994 when John Nash got awarded a Nobel Peace Prize.
Terminologies linked with game theory 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 get distinguished into either mixed or pure strategy.
Assuming that m defines the set of strategies that player A could make use, while n indicates the strategies usable by player B. Pi indicates the probability of choosing the alternative player A, i=1, 2, 3, 4,…m. assume that qj becomes the probability of choosing j for player B, for j=1, 2, 3, 4, ——n. the probabilities summation of the different alternatives of each player becomes
Pure strategy: a case when a player identified 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 P1=1, P2=0, P3=0 and so on. The summation of the probabilities generates 1, P1+p2+P3+P4=1+0+0+0=1.
Mixed strategy: A player that makes use of more than a single strategy follows 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.
Payoff matrix: A payoff refers to a number indicating the outcome which a player desires. For random outcomes, a player might weigh the outcome probabilities. The payoffs anticipated determines 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 equilibriums commonly known as strategies equilibrium. The Nash equilibrium involves a list of strategies, one player entitled to a single strategy. The players limited to strategies such that they do not alter them unitarily since they would not attain 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 a dominating strategy when it generates 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 involves a person that plays with the intention of maximizing their playoff. 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 get 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 Maxinim value describes the maximum values belonging to the minimal gains. The strategies applied to get the maximum value is referred to as maximin strategy.
Minimax principle: The principle reduces the loss potential associated with maximum losses. The maximum loss accumulate for all player B’s alternatives, other than A. The minimum value of the maximum losses, referred to as, minimax value. The strategy applied in obtaining the minimax value is known as minimax strategy.
Saddlepoint: Games whose minimax values corresponds with the maximum values are referred to as saddle point. 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.
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, collection, processing, and storage of environmental information and also engage in communication with neighboring nodes when 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 network also help in detection of ambient scenarios, which include light, sound, movement, temperature and inventory management.
Wireless sensory networks involves a complete set up of a network implemented within a region, whereas the sensory nodes positions do not require 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 through assisting them locate survivors, letting the rescue team aware of the prevailing situation and identification of the risky places in the disaster setting.
The sensor nodes communicate to one another directly, or through an external Base Station (BS). It is possible to apply a big number of sensor 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
- Power Unit
Figure 3.1: Sensor Node Architecture
The ADC becomes responsible for converting the analog signals which 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 get transformed into digital signals whose meaning the system readily interprets.
The processing units performs 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 the 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 contain location identifying systems in most cases (Zeng, 2015). A mobilize 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 fields 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.
- User (Task Manager)
- Base Station
Figure 3.2 Typical Network communication architecture
The sink communicates to the users through the satellites or internet. Figure 3.3 below illustrates the protocols which apply in the sensor nodes and the sink. Zeng, (2015) argued that the network protocol illustrates the routing awareness, power efficiency, network participation and data integration. The protocol layers include transport layer, application layer, data link layer, network layer, and physical layer. Other layers include task management plane, and mobility management plane.
Figure. 3.3. Sensor Network Protocol
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 a 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 a power efficiency within the node alongside the data routes which the transport layer institutes. The transport layer maintains data flow when the network sensor requires that the data flow gets 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 monitors the power, mobility movement monitors the movement while the tasks management planes monitors the tasks distributed within the sensor nodes. The three planes allow the sensor nodes coordinate tasks, thus reducing the power consumed.
Wireless Sensor Networks have several areas of application not limited to environmental monitoring, military and health sector. The popularity of wireless network 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 makes the network lifetime get reduced, and additional effort needed to make its use efficient. The energy consumed within the networks sensor nodes ought to get reduced.
Research conducted in Wireless Sensor Networks designed sensor network algorithms that consume little power. Other research focused on sensor nodes 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 application increased in wireless sensor networks designs. The report applied the use of game theory for wireless sensor networks. Different research papers published between 2003 and 2013 regarding the application of game theory for wireless sensor networks. Different game theory methodologies 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 get considered. Non-cooperative game theory heavily applies in wireless sensor networks. Non-cooperative game theory exhibits the purchase, sales or utilize goods by the nodes depending on the virtual market prices. Nodes maximizes the profit potential through engaging in different actions. Profitability attained by a node depends on the action success. Non-cooperative game theory success depends on a single utility rather than the efforts by 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 with dynamic games, whereby a game is played severally and the participants view the previous outcomes before engagement the future games.
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 into payoffs for the players. The table 1 below indicated the wireless sensor networking game typical components.
|Game components||Wireless Sensor Network Components|
|Players||Wireless Sensor Network Nodes|
|Game strategies||Coding rate, modulation scheme, power transmission rate|
|Set of playoffs||Performance metrics|
Table 1: Wireless Sensor Networking Game Components
Different game theory models applicable depending on factors at hand like sum of gains or losses in the game, number of participants, strategies deployed, 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.
|Game theory methods||Associated terminologies|
Table 2. Game Theory Methods and Terminologies in Wireless Sensor Networks
Non-cooperative game theory relates with strategic choices analysis alongside explicit models which a player in the game follows based on their interests. Non-cooperative games get differentiated into several other categories, based on the game rules. Non-cooperative game theory get 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 form.
Dynamic game requires the person to follow a strategic decision, but on a 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 indicates 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 requires all participants to have full information regarding the strategy spaces, characteristics of other players and the payoff functions but does not matter in the case of incomplete information games. There are various categories of non-cooperative games, and their equilibrium concepts.
|Static game||Dynamic game|
|Complete information games||Complete information static games||Complete information dynamic games|
|Incomplete information games||Incomplete information static game
Bayesian Nash equilibrium
|Incomplete information dynamic game
Perfect Bayesian Nash Equilibrium
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 applies in congestion controls, distributed resource allocation, and spectrum sharing.
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 the 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, 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 focuses on fairness, effectiveness and collective rationality so that all participants enjoy the payoffs while they also contribute.
Nodes come together into a coalition, with the intention of reducing energy consumption in the wireless sensor networks and prolong 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 which 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 categorized into a single group
- Sensors nodes that portend 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 depends on their contribution level and the strategies which they follow.
Shapley value comes from cooperative game theory. Shapley values becomes an important concept in game theory, representing single-valued solutions within cooperative games 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 create 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.
Ad hoc networks occupy a big position in networking and wireless communication for years. Ad hoc networks involve multi-hop networks that configure on their own and lack 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 networks 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 amongst the members of the network.
Nodes that run through a wireless sensory networks engage in autonomous decision making. However, the decisions might be made in regards 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 provided. Nodes or players are organized in a manner that they offer value to the network. Nodes might share objectives, but their perspectives of 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.
Game theory allows players 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 getting adopted in everyday technology, but it becomes 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 to within a wireless network. It is not possible to identify the conflict areas when the network gets designed, but game theory offers the potential options when the network becomes operational. Game theory models reveal important features that allows one 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 towards resolving the network issues.
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