A Game Theoretic Approach for Interuser Interference Reduction in Body Sensor Networks

4.1. Cost Function

In the purpose of reducing the effect of interuser interference in the network, the selection of the channel and transmission power is modeled as a noncooperative game between different BSNs (users). In this game, each user is a rational player. They observe local conditions and neighbors' actions and independently adapt their strategy using no-regret learning algorithm to minimize the interuser interference. Obviously, this framework of the noncooperative game is propitious to solving the problem of the interuser interference in BSN. In the noncooperative game, the cost function normally represents the hate of a selfish user, who wants to minimize its own loss. Similarly, a player in our game may somehow modify its channel and transmission power in such a way that can not only decrease its own loss but also increase interferences to others. Due to the energy limitedness of the control node, the desired cost function should take account of the SINR and power utilization. Thus, similar to [34, 35], the cost function of each user that considers the tradeoff between attaining high SINR and maintaining lower power utilization is expressed as

u i ( σ i , σ - i ) = τ i ( γ i 0 - γ i j ) 2 + ξ i p i j , ρ i j = 1 ,

(1)

γ i j = G i p i j ∑ k = 1 , k ≠ i M ( S k p k j / ( τ k i ) δ ) + η i ,

(2)

G i = S i d i δ ,

(3)

Formally, based on (1) and (2), the cost function is defined as follows:

u i ( σ i , σ - i ) = τ i ( γ i 0 - G i p i j ∑ k = 1 , k ≠ i , ρ k j = 1 M ( S k p k j / ( τ k i ) δ ) + η i ) 2 + ξ i p i j i , ρ i j = 1 .

(4)

In the game, the goal of user b i is to attain high SINR and minimize power utilization over the channel that it chooses. It is worthwhile to note that there is not message exchange in the game. The cost distribution of other users σ - i is not available for user b i ; however, b i can get the aggregate response I i j ( σ - i ) that is, the interference from other users plus noise. To perform (5), b i needs to observe the local information I i = { I i j ( σ - i ) , for all c j } . Based on the information, the following best response is adopted by every user in the system:

π i ( I i ) = arg min ⁡ σ i ∈ Λ i u i ( σ i , I i ) ∀ b i ∈ B ,

(5)

4.2. Nash Equilibrium in the Game

In order to analyze the outcome of the game, we will give how the game will be played by rational players using the concept of Nash Equilibrium (NE), which states that at equilibrium every player selects a cost-minimizing strategy given the strategies of other players.

The Nash Equilibrium ρ * p * = [ ρ 1 j 1 * ( p 1 j 1 * ) * , ρ 2 j 2 * ( p 2 j 2 * ) * , … , ρ N j N * ( p N j N * ) * ] in the game is mathematically defined as

u i ( ρ i j i * ( p i j i * ) * , ρ - i j p - i j ) ≤ u i ( ρ i ′ p i ′ , ρ - i j p - i j ) , ∀ b i ∈ B , ∀ ρ i ′ p i ′ ∈ Λ i ,

(6)

Proof.

Let ∑ k = 1 , k ≠ i , j k ≠ j i M S k p k j / ( υ k i ) δ + η i = I i j i ( p - i j i ) ， so (4) can be written as

u i ( p i j i , p - i j i ) = τ i ( γ i 0 - G i p i j i I i j i ( p - i j i ) ) 2 + ξ i p i j i , ρ i j i = 1 .

(7)

Taking the derivative of (7) with respect to p i j i and equating it to zero for p i j i gives the following condition:

2 τ i ( γ i 0 - G i p i j i I i j i ( p - i j i ) ) ( - G i I i j i ( p - i j i ) ) + ξ i = 0 ,

(8)

that is,

2 τ i G i 2 p i j i ( I i j i ( p - i j i ) ) 2 - 2 τ i γ i 0 G i I i j i ( p - i j i ) + ξ i = 0 .

(9)

Thus, we can get

p i j i = γ i 0 I i j i ( p - i j i ) G i - ξ i ( I i j i ( p - i j i ) ) 2 2 τ i G i 2 .

(10)

Due to p i j i ≥ 0 , we can get

γ i 0 I i j i ( p - i j i ) G i - ξ i ( I i j i ( p - i j i ) ) 2 2 τ i G i 2 ≥ 0 ,

(11)

that is,

τ i ξ i ≥ I i j i ( p - i j i ) 2 γ i 0 G i .

(12)

For given values of τ i , ξ i , γ i 0 , G i , and p i j i , the quadratic (10) in I i j i ( p - i j i ) has a real solution if and only if

( γ i 0 G i ) 2 - 4 ( ξ i 2 τ i G i 2 ) p i j i ≥ 0 ,

(13)

that is,

p i j i ≤ τ i ( γ i 0 ) 2 2 ξ i .

(14)

Because the transmission power is p i j ∈ [ p min , p max ] , based on inequality (14), τ i / ξ i must satisfy

τ i ξ i ≥ 2 p max ⁡ ( γ i 0 ) 2 .

(15)

According to [36], in order to make the game converge to a unique fixed point, a fixed point from (10) should satisfy the following properties: (1) positivity; (2) monotonicity; (3) scalability. Therefore, based on [34], we can get

τ i ξ i > I i j i ( p - i j i ) γ i 0 G i .

(16)

Based on (12), (15), and (16), we can get that the noncooperative game has a unique NE for the transmission power ( p i j i ) * on the channel c j in the condition of (15) and (16).

In order to configure the weighting factors τ i and ξ i dynamically to adapt to different situations, we propose a weighing factor configuration algorithm based on Theorem 1 as shown in Algorithm 1. In the scheme, the control node collects the minimum remaining battery capacity ca min of sensor nodes deployed in the same BSN and observes the local information I i j i ( p - i j i ) . Then, the relation between τ i and ξ i can be determined based on I i j i ( p - i j i ) according to the relation between the minimum remaining battery capacity ca min and the maximum battery capacity ca i . It is worth noting that the maximum battery capacity of each sensor deployed in the same BSN is assumed to be the same. In the algorithm, α i and β i are two negative constant parameters. We can find that the greater the minimum remaining battery capacity is, the greater the value of τ i / ξ i is.

Algorithm 1: Weighing factor configuration algorithm.

A probability distribution ω is a correlated equilibrium (CE) over the set of user strategies if and only if the following inequality is satisfied:

∑ ρ - i ∈ Λ i ω ( ρ i , ρ - i ) [ u i ( ρ i ′ , ρ - i ) - u i ( ρ i , ρ - i ) ] ≥ 0

(17)

4.3. No-Regret Learning Algorithm for the Game

In order to analyze the behaviour of the selfish users in the noncooperative interuser interference reduction game, we resort to the regret minimization learning algorithms [38]. No-regret learning algorithms are probabilistic learning strategies that specify that players explore the space of actions by playing all actions with some nonzero probability and exploit successful strategies by increasing their selection probability. In the game, each user b i can determine the probability distribution of strategy σ i based on the average regret at the iteration period φ ∈ { 1 , … , t } , and thus it can select its action based on the history of actions of every user. The regret is defined as the difference between the costs caused by distinct strategies, and thus, for every two distinct strategy profiles ( σ i φ , σ - i φ ) and ( σ i ( ( p i j ) * ) , σ - i φ ) , user b i uses the strategy profile ( σ i ( ( p i j ) * ) , σ - i φ ) to replace the strategy profile ( σ φ , σ - i φ ) and the user b i feels a regret:

r i φ ( σ i ( p i j ) * ) = u i ( σ φ ) - u i ( σ i ( p i j ) * , σ - i φ ) .

(18)

The resulting historical cumulative regret of user b i from ( σ i φ , σ - i φ ) to ( σ i ( ( p i j ) * ) , σ - i φ ) up to iteration t is

D i t ( σ i ( p i j ) * ) = max ⁡ { 1 t ∑ φ = 1 t [ u i ( σ φ ) - u i ( σ i ( ( p i j ) * ) , σ - i φ ) ] , 0 } .

(19)

Based on (19), the probability ω i assigned to the action σ i ( p i j ) * of user b i at iteration t + 1 is calculated by

ω i t + 1 ( σ i ( p i j ) * ) = D i t ( σ i ( ( p i j ) * ) ) ∑ σ i ( p i j ′ ) ∈ Λ i D i t ( σ i ( ( p i j ′ ) * ) ) .

(20)

The above learning algorithm can converge to Nash equilibrium in the game, and thus each user b i repeats calculations based on (19) and (20), and then it can determine its strategy at time step t + 1 as

ρ i t + 1 ( σ i ( ( p i j ) * ) ) = { 1 if t + 1 ω i ( σ i ( ( p i j ) * ) ) = max ⁡ { ω i t + 1 } . 0 otherwise

(21)

By following the no-regret learning adaptation process, the user can learn how to choose the channel and transmission power to minimize the cost through repeated play of the game. Algorithm 2 presents the pseudocode of the iterative no-regret learning algorithm used in the interuser interference reduction game. At the initial step, each user b i randomly selects its channel c j i with equal probability as the initial action. The optimal transmission power p i j i and cost u i ( σ i , σ - i ) on the channel c j i will be calculated based on the interference plus noise measured. Based on p i j i and u i ( σ i , σ - i ) , the probability of b i for the current strategy is updated accordingly. If there exists a channel that has not been selected randomly with equal probability, then user b i repeats the step of random channel selection with equal probability. When the maximum ω i ( σ i ( p i j ) * ) in the probability distribution ω i has exceeded the threshold ϕ, user b i will get the solution ρ i j i * ( p i j i * ) * , otherwise it will select a channel based on the probability distribution ω i randomly and repeat its learning process in a round-robin manner to favour the strategy with minimum interference plus noise.

Algorithm 2: No-regret learning algorithm for the game.

It is worth mentioning that the no-regret learning algorithm is a distributed iterative best-response scheme. In the noncooperative game, based on the information available locally, each player determines its own strategy (i.e., the channel and transmission power) to ensure that the solution converges. The convergence of the solution indicates that every user achieves its desirable operating point, where no user intends to change its strategy.

5.1. Simulation Model and Method

The performance of the proposed interuser interference reduction scheme is evaluated by extending the Castalia simulator [39] to support the simulation of interuser interference in BSN. Castalia is an open source, discrete event-driven simulator designed specifically for WSN, BAN, and generally networks of low-power embedded devices based on OMNeT++ [40].

For simulation purposes, five BSNs are distributed over a 10 m × 10 m square area, and each BSN simulates a typical on-body sensor network, in which sensors measure a person's physiological parameters. Each BSN has a control node and three biosensors (i.e., ECG sensor, SpO2 sensor, and temperature sensor). All sensor nodes adopt Castalia standard CC2420 IEEE802.15.4 radios. The number of available nonoverlapping frequency channels for each BSN is five in the experiment. The detailed configuration of simulation parameters is shown in Table 2. Note here that the configuration of parameters may vary depending upon the kind of sensors. In order to evaluate the performance of the scheme to copy with interuser interference for the different user densities and system typologies generated by the mobility of BSN users, we set up four representative system topologies to perform the simulation. Figure 3 presents the BSN user distributions of four representative system topologies during the simulation, where the dotted line represents the interuser interference between two users. In the initial state, all BSN users use the same channel and select a random transmission power level as the initial strategy. In our experiment, we compare the performance of the system in the initial state and the final state after convergence to demonstrate the performance of the DISG scheme.

OPEN IN VIEWER

Table 2

Simulation parameters.

Parameters	Value
Number of BSNs	5
Area	10 m × 10 m
Number of sensor types	3 { ECG , SpO 2 , Temperature }
Number of available nonoverlapping frequency channels	5 { 11 , 12 , 13 , 14 , 15 }
Transmission power set (mW)	{ 29.04 , 32.67 , 36.3 , 42.24 , 46.2 , 50.69 , 55.18 , 57.42 }
Wireless channel model	Log shadowing wireless model
Path loss exponent	2.4
Collision model	Additive interference model
Physical and MAC layer	IEEE 802.15.4 standard
Application type	Event-driven

OPEN IN VIEWER

Figure 3

System topology.

5.2. Simulation Results

We repeated the simulations several times and got similar results in each trial. In the following, we present a representative result from one trial and analyze it in detail.

The convergence property of the proposed no-regret learning algorithm for the interuser interference reduction game is evaluated first to demonstrate the correctness and effectiveness of the scheme. From Figure 4 that shows the user distribution on different channels over time during the simulation of the proposed no-regret learning algorithm for the topology 4, we can find that, at the beginning of the experiment, all BSN users select their channels randomly with equal probability, and, at last, the learning solution converges to a stable and desirable state (i.e., the equilibrium state) after a few iterations where all BSN users select different frequency channels to minimize interference.

OPEN IN VIEWER

Figure 4

User distribution on different channels.

As performance measures for the proposed interuser interference reduction scheme, we consider the average SINR of the system (Figure 5), the packet delivery rate (PDR) (Figure 6), and the energy consumption of per delivered date byte (Figure 7) in the simulation.

OPEN IN VIEWER

Figure 5

Average SINR initially and after convergence.

OPEN IN VIEWER

Figure 6

Average PDR initially and after convergence.

OPEN IN VIEWER

Figure 7

Energy consumption of per delivered byte initially and after convergence.

As can be seen from Figure 5, in all system topologies, the average SINR of the system after convergence is obviously higher than that of the initial state owing to the adaptive selection of strategies. In addition, the higher the user density is, the more obvious the effect of our scheme is. In all topologies, the average SINR of the system in the final state is almost 90 dB.

In Figure 6 we compare the obtained average PDR of the system after equilibrium using our scheme against the initial average PDR in different typologies. The result shows that the system after convergence achieves higher average PDR than the system without operating our scheme in all system topologies.

As illustrated in Figure 7, the average energy consumption per delivered data byte of the system in the final state is lower than that of the system that has not performed our scheme. The reason is that the retransmission overhead in the system is reduced by ensuring the QoS of the system after performing our scheme. Moreover, trade-off between obtaining high SINR and maintaining low power utilization also can reduce power dissipation.

5.3. Discussions

From the above described simulation results, we can conclude that, in the system with DISG, an equilibrium state is reached after a few iterations of no-regret learning, where each BSN user selects the suitable strategy to reduce the effect of interuser interference. The system with DISG can provide the appropriate SINR by minimizing the interuser interference, and thus the average PDR is enhanced compared with the system without DISG. The average energy consumption of the system with DISG is reduced owning to the reduction of retransmission overhead as well as the trade-off between SINR and power utilization. In addition, DISG can be applied to different topologies generated by the mobility of BSN users. Therefore, DISG can reduce the effect of interuser interference effectively to ensure specific QoS requirement and save transmission energy at the same time to prolong the lifetime of network.