Cooperative Game Theory and Its Application in Localization Algorithms

1. Introduction

Game theory is a field of applied mathematics for analyzing complex interactions among entities. It is basically a collection of analytic tools that enables distributed decision process. Game theory (GT) provides insights into any economic, political, or social situation that involves individuals with different preferences. GT is used in economics, political science and biology to model competition and cooperation among entities, and the role of threats/punishments in long term relations. Contemporary social science is based on game theory, economics, and psychology in which mathematical logic is applied. The formation of coalitions or alliances is omnipresent in many applications. For example, in political games, parties, or individuals can form coalitions for improving their voting power. Recently, computer science and engineering have been added to the list of scientific areas applying GT.

While inoptimization theory the goal is to optimize a single objective over one decision variable, game theory studies multi-agent decision problems. In social sciences and economics, the focus of game is the design of right incentives/payoffs; in engineering it comes to efficiency – how to design efficient decentralized schemes that take into account incentives. However, there are still similarities when applying game theory to different disciplines. For example, a measurement allocation framework for localization in wireless networks, based on the idea to allocate more measurements to the nodes which contribute more, mimics a capitalist society where the gains are mostly reinvested where more profit is expected. It also replicates the concept of natural selection in population genetics.

In general, a game consists of a set of players (decision makers), while each player has its strategy, whereby utility (payoff) for each player measures its level of satisfaction. Each player’s objective is to maximize the expected value of its own payoff (Myerson, 1997).

(Srivastava V., et all, 2005) proposed a mapping of network components to game components according to the following table:

Network component	Game component
Nodes	Players
Available adaptations	Action set
Performance metrics	Utility function

Table 1

Classification of coalitional games

Game theory can be applied to communication networks from several aspects: at the physical layer, link layer and network layer. However, there a certain challenges when applying game theory principles to wireless networks. For example, GT assumes that the players act rationally, which does not exactly reflect real systems. Furthermore, realistic scenarios necessitate complex models, yet the main challenge is to select the appropriate utility function, due to a lack of analytical models that would map each node’s available actions to higher layer metrics.

1.1. Notation

A normal form representation of a game is given by G = <N, S_i, {u_i}>, where N = {1,…,n} is the set of n of players. We indicate an individual player as i ∈ N and each player i has an associated set S_i ={s_i¹,…,s_i^m} of possible strategies from which, in a pure strategy normal form game, it chooses a single strategy s_i ∈ S_i to be realized. s= {s₁,…,s_N} is the strategy profile of N players, i.e., the outcome of the game, while s_-i is the strategy profile of all players but the i-th, and {u_i} = {u₁,…,u_N} is the utility function of the i-th player. The utility function measures the preferences of each player to a given strategy, assuming the strategies of other players are known.If s is a strategy profile played in a game, then u_i(s) denotes a payoff function defining i’s payoff as an outcome of s.

There are two main branches of game theory: cooperative and non-cooperative. Non-cooperative GT addresses interactions among individual players, each aiming to achieve their own goal, namely improving its utility, or reducing its costs. Specifically, in cooperative games the utility does not only depend on a single node’s strategy, but also on the strategies of other nodes within a coalition. Hence, cooperative game theory is more elaborate. Especially in realistic situations where entities can participate in several coalitions, the potential structure of these coalition allocations is more complex;thus there is a need to for concepts that could reduce the complexity, without identifying and comparing all of the 2ⁿ – 1 possible coalitions.

One of the concepts for solving non-cooperative games is the Nash equilibrium. Nash equilibrium is a stable solution of the game such that no player has reason to unilaterally change its action, since it may not improve its utility function. More precisely, a strategy profile set s*= {s*₁,…,s*_N} is a NE if for ∀s_i∈S_i and for ∀i ∈ N, u(s*_i, s*_-i) ≥ u(s_i, s*_-i). A strategy set that corresponds to the Nash equilibrium signifies a consistent prediction of the outcome of the game. In other words, if all players predict that Nash equilibrium will occur, there is no player in the game that has incentives to choose a different strategy. Any game allowing mixed strategies has at least one NE. However, some pure strategy normal form games may not have a NE solution at all. Therefore it is relevant to formulate the utility function in such a way that the game has at least one equilibrium point.

When efficiency is important, Pareto Optimality is used. The existence of Nash Equilibrium does not assure that the outcome of a game will be beneficial for all players. Mathematically formulated, a strategy set s= {s₁,…,s_N} is Pareto optimal if and only if there exists no other strategy set t= {t₁,…,t_N} such that u_i(t) ≥ u_i(s) for ∀i ∈N, and for some k ∈N, u_k(t) >u_k(s)

In other words, Pareto optimal outcome cannot be improved upon without hurting at least one player.

In this chapter we will focus on cooperative game theory and its application in localization algorithms.

2. Coalitional games in wireless communications

A coalition formation game is uniquely defined by the pair (N, v). N = {1,2,…,N} denotes the set of players, e.g., network entities, pursuing to form sets in order to collaborate with each other. Any nonempty subset S ∈ N is called a coalition. Coalitions with cardinality |S| = 1, are called singleton coalitions and N is called the grand coalition. The set of all coalitions in a game is called coalition structure and is denoted by P. v denotes the coalition value which quantifies the worth of a coalition in a game.

2.1. Coalitional games – background

Coalitional games in characteristic form are classified into two types based on the distributing of gains among users in a coalition:

1. A transferable utility (TU) game where the total gain achieved can be apportioned in any manner between the users in a coalition subject to feasibility constraints, and

2. A non-transferable utility (NTU) game where the apportioning strategies have additional constraints that prevent arbitrary apportioning. Each payoff is dependent on joint actions within coalition.

In TU games, the cooperation possibilities of a game can be defined by a characteristic function v that assigns a value v(S) to every coalition S. Here v(S) is called the value of coalition S, and it characterizes the total amount of transferable utility that the members of S could gain without any help from the players outside of S. In general, we use the term coalition structure to refer to any mathematical structure that describes which coalitions (within the set of all 2ⁿ – 1 possible coalitions) can effectively negotiate in a coalitional game.

The overall goal is to find a coalition structure such that no group of players has the incentive to leave it – so called stable coalition structure. Superadditivity is defined in TU games as a property of the characteristic function:

$$v\left(S_{1}U{S}_2\right)\ge v\left(S_1\right)+v\left(S_2\right); \forall S_1,S_2\in N, S1\cap S2=\varnothing .$$E1

In other words, a TU game is superadditive if cooperation is always rewarding. Thus, grand coalition, i.e., the coalition comprising all sensors, is beneficial. The most notable solution concept for the coalition formation in superadditive games is the core; other solutions include Shapley value, kernel, and Nucleolus.

The superadditivity concept can be extended to NTU games, by:

$$\left\{x\right|{\left(x_i\right)}_i{}_{\in S1}\in v\left(S_1\right),{\left(x_j\right)}_j{}_{\in S1}\in v\left(S_2\right)\}\subseteq v\left(S_{1}U{S}_2\right)$$E2

In case of TU games, goal is to find a coalition structure that maximizes the total utility, while in NTU games it is the structure with Pareto optimal payoff distribution. A centralized approach can be used, but it is generally NP-complete. The reason is that finding an optimal partition requires iterating over all the partitions of the player set N. The number of partitions grows exponentially with the number of players in N. For example, for a game where N has 10 elements, the number of partitions that a centralized approach has to go through is 115,975 (easily computed through the Bell number (Saad W., et all, 2009c). Therefore, using a centralized approach for finding an optimal partition is, generally, computationally complex and not very practical. Nevertheless, many applications require the coalition formation process to take place in a distributed manner, so that the players have autonomy on the decision whether or not to join a coalition. Indeed, the complexity of the centralized approach has initiated a growth in the coalition formation literature, with the goal to find low complexity and distributed algorithms for establishing coalitions.

A novel classification of coalitional games has been proposed in (Saad W., et all, 2009c). Games are grouped into three types: canonical games, coalition formation games and coalitional graph games. Their properties are shown in the following table.

Canonical coalitional games	Coalition formation games	Coalitional graph games
Grand coalition is the optimal structure	Resulting coalitional structure depends on gains and costs	Interaction of players depends on communication graph structure
Goal: stabilize the grand coalition	Goal: form appropriate coalition structure	Goal: stabilize grand coalition or form network topology taking into account the communication graph

Table 2

Classification of coalitional games

In this chapter we will focus on coalition formation games.A generalized approach to coalition formation has been proposed in (Apt & Witzel, 2006). The notion of stable partition is used when there does not exist any other partition that would improve the total gain. In order to illustrate the coalition formation procedure, an abstract preference operator $$⊳$$ has been introduced, and coalitions are being transformed using merge and split rules.

2.2. Applications to communication networks

From the communication networks perspective, there is the need for developing distributed and flexible wireless networks, where the units make independent and rational strategic decisions. In addition, low complexity distributed algorithms are required, to capably represent collaborative scenarios between network entities. Non-cooperative games have been mainly applied for applications such as spectrum sharing, power control or resource allocation – mainly settings that can be seen as competitive scenarios. On the other hand, cooperative game theory provides analytical tools to study the behavior of rational players in cooperative scenarios. In particular, coalitional games show to be a very powerful tool for designing fair, efficient and robust cooperation strategies in communication networks. In order to highlight an expanding application field, in the following section we will give some examples on use of cooperative game theory for communication networks, and specifically for localization purposes.

Physical layer security has been studied via coalitional games in (Saad W., et all, 2009a), (Saad W., et all, 2009b). In a distributed way, wireless users organize themselves into coalitions (see Figure 1.) while maximizing their secrecy capacity - maximum rate of secret information sent from a wireless node to its destination in the presence of eavesdroppers (Saad W., et all, 2009a). This utility maximization is taking into consideration the costs occurring during information exchange. On the other hand, (Saad W., et all, 2009b) introduces a cooperation protocol for eavesdropper (attacker) cooperation. Here the utility function is formulated to capture the damage caused by the attackers, and the costs in terms of time spent for communication among the eavesdroppers. In both cases, independent disjoint coalitions will form in the network, as the grand coalition would involve various communication costs.

Figure 1.

Wireless users organized into coalitions

(Mathur S., et all, 2006) and (Mathur S., et all, 2008) consider coalition structures in a wireless network where users are permitted to cooperate, while maximizing their own rates. Here both transmitter and receiver cooperation in an interference channel is studied. Several models have been analyzed: a TU and an NTU model, and with perfect and partial cooperation. In (Mathur S., et all, 2006), the feasibility and stability of the grand coalition for all cases was evaluated, while the work in (Mathur S., et all, 2008) is focused on stable coalition structures. In (Saad W., et all, 2008) a game theoretical framework for virtual MIMO has been proposed, where single antenna transmitters self-organize into coalitions. The utility function denotes the total achieved capacity, and also includes the power constraint to account for the costs.

In (Hao X., et all, 2011) the multi-channel spectrum sensing problem is formulated as a coalitional game, where players are secondary users that cooperatively sense the licensed channels of primary users. The utility of each coalition reflects the sensing accuracy and energy efficiency. Distributed algorithms have been proposed to determine a stable coalition structure, maximizing the overall utility in the system. More game theory based solutions for spectrum sensing in cognitive radio have been proposed in (Khan Z., et all, 2010) and (Saad W., et all, 2009c).

A network-level study using coalition formation has been performed in (Singh C., et all, 2012), considering a scenario where service providers are cooperating in order to enhance the usage of the available resources. Particularly, different providers may serve each other’s customers and thereby increase the throughput and reduce the overall energy consumption. The model supports multi-hop networks and is not limited to stationary users and fixed channel conditions. A game theory based framework is used to determine optimal decisions and a rational basis for sharing the aggregate utility among providers. The optimal coalition structure can be obtained by means of convex optimization.

Other applications of game theory include packet forwarding in ad hoc networks, distributed cooperative source coding, routing problems, and localization algorithms, which will be more elaborated in the next chapter.

3. Game theory for localization algorithms

The expansion and enhancement of wireless and mobile devices has aroused the demand of context-aware applications, in which location is often viewed as one of the most important contexts. Those applications include pervasive medical care, wireless sensor network surveillance, mobile peer-to-peer computing etc. The essential purpose of wireless sensor networks (WSN) is to provide information about observed events. Before the WSN can be exploited for various applications, knowledge about sensors’ locations is crucial, as otherwise the data might become meaningless. Furthermore, location information can be used to improve the communication system itself. Geo-location information can serve as complementary data to estimate and predict critical parameters for improving wireless communication networks, such as setting up location dependent load balancing schemes (Yanmaz E. & Tonguz O.K.). Several studies have shown how the efficiency of available radio resources can be improved by the availability of position information to provide accurate scheduling and link adaptation (Tang S., et all, 2009), or even the prediction of required resources in a highly dynamic scenario. Additionally, localizing the nodes can help reduce power consumption in multi hop wireless networks.

Global navigation satellite systems (GNSS), such as Global Positioning system (GPS) or the European satellite navigation system Galileo, are providing positioning information. However their accuracy strongly depends on the scenario. Especially in dense urban or indoor environments, navigation based on GNSS becomes inaccurate or impossible, since the necessary amount of 4 directly visible satellites is not reached. In order to provide accurate MT position estimation, the MT position shall be estimated with alternative techniques focusing on radio signals which are provided by the terrestrial RANs itself. The rapid deployment of WLAN and WPAN technologies, especially in dense indoor environments, made it another compelling choice for localization, relying only on the existing network infrastructure.

Generally, the localization process assumes a number of location aware nodes, called anchors. In a typical two-stage positioning system, the first phase is the ranging phase, where nodes estimate the distances to their neighbors by observing time of arrival, received signal strength or some other distance dependent signal metric. In the second phase, nodes use the ranging information and the known anchor position for calculation of their coordinates.

Figure 2.

Two-stage positioning system

One simple way for position calculation is trilateration / triangulation, based on the least square algorithm. Trilateration uses distance estimates to anchor nodes as input, and estimates target’s position based on geometric properties of triangles. Each estimated distance represents the radius of a circle centered at the corresponding reference node. For 2-D positioning, measurements from at least three reference nodes are required, and the location is obtained as the intersection of circles. This method is also used for GPS. Having in mind the errors in estimated distances to the anchors, the geometrical trilateration technique can only provide a region of uncertainty, instead of a single point. Therefore the solution is based on iterative algorithms to obtain the node position by formulating and solving a set of nonlinear equations.

The availability of positioning information depends on the existing infrastructure such as GPS satellites or base stations. Cooperative positioning techniques are used in scenarios where non-cooperative solutions are not feasible, or do not perform well in terms of accuracy, cost and complexity. The challenge is to allow nodes which are not in range of a sufficient number of anchors to be located, and hereby increase localization performance in terms of both accuracy and coverage. This can be achieved by means of iterative multilateration, among other solutions. Iterative multilateration is a way to expand localization coverage throughout the network in a step-by-step fashion, allowing also nodes which are not in range of a sufficient number of references to be localized. In this sense, coverage is the fraction of nodes that have an accurate position estimate. It follows an iterative scheme: once an unknown node estimates its position, it becomes an anchor and broadcasts its position estimate to all neighboring nodes. The process is repeated until all nodes that can have three or more reference nodes obtain a position estimate. As a newly localized node is becoming new anchor for its neighbors, the estimation error of the first node can propagate to other nodes and eventually get amplified. Over iterations the error could spread throughout the network, leading to abundant error in large topologies.

Figure 3.

Iterative multilateration

The number of actively participating nodes should be kept to a minimum, and therefore an appropriate cooperation subset has to be chosen, while the other nodes can be ignored. Such a restrictive and selective use of references is crucial in networks with limited resources. A frequently used method is to select the nearest k anchor nodes. However, this method does not take into account node geometry. Therefore other metrics such as geometric dilution of precision, Cramer Rao lower bound or stochastic observability are more appropriate.

The geometric conditioning on localization accuracy is derived in the GDOP (geometric dilution of precision) metric (Spirito M.A., 2001). In brief, when reference nodes are well separated around the target, the GDOP is lower.

Localization can be defined as an estimation problem where measurements like wireless signal strength, angle or time of arrival are provided to an estimator (i.e. the localization algorithm) to obtain the most likely position in the assumed coordinate system. The Cramer Rao Lower bound (CRLB) provides a lower bound on covariance of any unbiased estimator. In case of localization, the CRLB captures information about node geometry and ranging quality, i.e., quality of distance estimates obtained from noisy measurements of received signal strength (RSS), time of arrival (TOA) or angle of arrival (AOA) (Patwari N., et all, 2003). Since the variance of position estimates is associated to the mean error, the lower bound on variance can be seen as the upper bound on accuracy.

3.1. Use of game theory in localization algorithms

Recently game theory has been applied in localization algorithms, mainly for modeling the cost-performance trade-off and for selection of reference nodes. The work in (Ghassemi F. & Krishnamurthy V., 2008a) applies game theory for sensor network localization, namely for measurement allocation among reference nodes localizing the target. The localization process has been modeled as a game belonging to the class of weighted-graph games. For such a representation, the vertices correspond to the players, and the coalition value can be obtained by summing the weights of the edges that connect a pair of vertices in the coalition with self-loop edges only considered with half of their weights. A weighted-graph game can therefore be well represented by $$\frac{N(N-1)}{2}+N$$ weights, in contrast to 2N numbers which are usually required to represent a cooperative game. Basic idea is to allocate more measurements to nodes that contribute more to the localization process. The allocation algorithm has been integrated into a Bayesian estimator. In (Ghassemi F. & Krishnamurthy V., 2008b), utility is defined as information gain from a node, i.e. the mutual information between the prior density of target position and the measurement. Additionally, a price for transmission is included to account for the current energy level in the nodes, and the energy needed for data transmission.

The algorithm proposed in (Moragrega A., et all, 2011) assumes a number of static anchor nodes, strategically placed to guarantee coverage to all unknown nodes. Anchors transmitting with lower energy can provide coverage to a smaller number of nodes; aim is to minimize power consumption at the anchor nodes, while assuring desired localization accuracy. The metric for positioning quality is the GDOP. The problem has been formulated as a noncooperative game, using Nash equilibrium as solution concept

In (Bejar B., et all, 2010) the coalition formation within the set of neighboring anchors helps reduce communication costs. Using only a subset of available reference nodes does not necessarily degrade the accuracy, since some of them provide redundant information. In some situations it might be even useful to discard ranging information from some reference nodes, after they have been identified as unreliable due to biases in the measurements. This paper the localization problem has been defined as a coalitional NTU game, where coalitions are formed based on the merge and split procedure. The utility function is defined to account for both a quality and cost indicator. While the quality function accounts for inconsistencies between each node’s measured distance and the final joint estimated distance within the coalition, the cost function is related to communication costs. The target tracking task based on coalition formation has been implemented using a Kalman filter. For the coalition formation approach a higher mean estimation error has been observed than for grand coalition, i.e., when all nodes contribute to the tracking process. Nevertheless, in terms of communication costs the proposed scheme provides significant savings.

(Ghareshiran O. N. & Krishnamurthy V., 2010) proposes a dynamic coalition formation algorithm used for energy saving in multiple target localization. Assuming that nodes in sleep mode do not record any measurements and thereby save energy in both sensing and transmitting data, the optimization problem is formulated to maximize the average sleep time of all nodes in the network, assuring that targets are localized with desired accuracy. An important contribution is exploitation of spatial correlation of sensor readings. Accuracy metric used is the determinant of the Bayesian Fisher information matrix (B-FIM). The characteristic function is formulated in a way that larger coalitions of sensors do not necessarily lead to longer sleep times. This is mainly due to the fact that the B-FIM, depending on both relative angles and distances of sensors to the target, does not automatically increase as the number of sensor nodes in a coalition goes up. The trade-off between performance and average sleep time allocated in the network is demonstrated via Monte Carlo simulations.

4. Scenario

We propose the use of cooperative non‐superadditive games for modeling localization algorithms. As stated in the previous section, a typical localization process consists of the ranging phase, where nodes estimate the distances to their neighbors, and a second phase where nodes use the ranging information and the known anchor position to calculate their coordinates. In a dense network one can assume a large number of available anchor nodes. However, transmitting and processing all the obtainable information would consume immense power, without necessarily leading to better localization performance. This is due to the fact that not all the anchors provide reliable measurements, what leads to erroneous distance estimates. Furthermore, the geometry of selected reference nodes shows to have significant impact on localization accuracy, what will be extensively elaborated in our work. Assuming that at each time instant a target has several neighboring anchor nodes in near vicinity, and different coalitions can be formed, the considered scenario is illustrated in Fig.4.

Figure 4.

Scenario

We propose an algorithm for reference node selection based on coalitional games. We model the localization process as a cooperative game, and formulate the corresponding utility function. We define the node selection optimization as one that maximizes the accuracy subject to constraints given by nodes’ limited processing capacity. Position estimates are obtained using the linearized least squares algorithm (trilateration).

4.1. Ranging error

We assume that the distance estimates between nodes are obtained using RSS measurements. We use the standard lognormal model for RSS with path loss parameter n_pand shadowing variance Ϭ²_RSS. Assuming that the received power P_i,j between nodes i and j is lognormal, the random variable P_i,j (dBm) =10logP_i,j is Gaussian. RSS based distance estimates are obtained using the lognormal model:

$$\widetilde{d_{i,j}}=d_{i,j}*{10}^{\frac{v_{i,j}}{10n_p}}$$E3

where v_i,j~ N (0, Ϭ²_RSS) and n_p is the path loss exponent. We used values for indoor scenarios n_p= 2.3 and Ϭ²_RSS = 3.92 dB as in (Patwari N., et all, 2003).

4.2. Utility function

The following parameters are relevant for reference node selection: number of references, quality of range estimates and geometry. Therefore we propose a node selection mechanism based on the Cramer Rao Lower Bound. Since the CRLB gives the upper bound on accuracy, the utility function has to be inversely proportional to the CRLB. Besides the quality indicator, utility function also has to reflect the cost. Cost is related to the energy spent for message exchanges between nodes, and is proportional to the distances of target node to reference nodes. Having in mind the energy consumption if all reference nodes were used for localization, the grand coalition is not optimal. Therefore we define the problem as a nonsuperaditive cooperative game. Since least square localization is not possible for less than three reference nodes, we set the value of all coalitions containing less than three nodes to zero. For the remaining ones, the coalition value of each chosen subset of nodes S will be of the form:

$v(S)=\frac{1}{CRL{B}_{i\in S}}-{\displaystyle \sum _{i\in S}\frac{d_{i,t}}{R}}$E4

Where CRLB_i∈S is the CRLB for the coalition S, d_i,t is the distance from node i ∈ S to the target t, and R is the transmission range, used to normalize the cost function. In order to illustrate the performance of coalition formation based node selection, we will perform an exhaustive search over all possible coalition sets containing three nodes. The results are presented in the next section.

5. Results

In this section we show through simulations how localization performance can be improved using cooperative game theory. Performance metrics are accuracy, complexity and latency.

Accuracy is evaluated as the Euclidean distance between the estimated position, and the node’s true location. Complexity is especially important in scenarios with low-power devices. In cellular scenarios computation is mainly performed in a central manner, e.g., at the base station with power supply, computational and processing complexity is not necessarily a limitation. In case of a moving target, its position needs to be updated with a frequency depending on the mobility model. Therefore it is important for the position calculation to be fast. We evaluate the localization accuracy as the root mean square error (RMSE) of location estimates. Complexity is assessed by means of amount of computation that has to be performed, while latency refers to the time needed to get a position estimate – particularly important for dynamic scenarios.

In our simulations we assume that the target node has a number of reference nodes in local vicinity, uniformly distributed within a 20 by 20 meters region. We show how appropriate selection of reference nodes outperforms the random selection, for cases of 10, 15 and 20 available references. We performed simulations for different node densities and compared them in terms of root-mean-square error (RMSE). We performed 1000 runs for each setup.

Figure 5.

Localization accuracy for random anchor selection and utility based selection.

The following scatter plot illustrates how the coalition value reflects the localization error.

In Fig.6 we assumed 10 available reference nodes. Besides accuracy, we will assess the complexity of the algorithm depending on the number of available reference nodes, namely considering sets of 10, 15, 20, 25 and 30 nodes, respectively. From each of these sets, three anchors providing the best results are chosen. We define computational complexity as the amount of time spent on localization, in this case on a simulation run. The measurement of computation time is calculated using MATLAB functions tic and toc, which return the elapsed time in seconds. Knowing that combinatorial complexity increases with number of elements, Fig. 7 shows the expected result, namely significantly higher complexity as the number of references increases.

Since we consider a static scenario, the latency factor is not of particular significance. However, one can consider the computation time in Fig. 7 as a latency parameter as well.

Figure 6.

Localization error vs. coalition value

Figure 7.

Computation time.

6. Conclusion

In this chapter we considered the application of coalitional games to communication networks, in particular to localization algorithms. Game theory proves to be a powerful tool for modelling various aspects of localization procedure, such as improved accuracy or energy saving. After giving an overview of the most significant contributions in the literature on this subject so far, we have proposed a localization procedure aiming to improve accuracy by selecting the references providing the best conditions in terms of channel conditions and node geometry. Besides providing better performance, choosing only a subset of available references contributes to resource saving. This is particularly important in wireless sensor networks, having in mind the nature of these networks, specifically the limited resources such as energy constraints, processing capacity and short transmission range.

The selection procedure is based on coalitional game theory. We proposed a utility function that reflects the contribution of each coalition to the localization accuracy, as well as a cost function related to energy consumption during the localization procedure. We compared the performance of utility based node selection vs. a random selection scheme. Even though the computational complexity significantly increases for a large number of available references, the achieved accuracy improvements make it a compelling concept for node selection.

Acknowledgement

This work has been performed in the framework of the ICT project ICT-248894 WHERE2, which is partly funded by the European Union. The work has been supported in part by the Portuguese Foundation for Science and Technology (Fundação para a Ciência e Tecnologia - FCT) under grant number SFRH / BD / 61023 / 2009.