博弈论在无线通信工程中的应用与挑战

5星 · 超过95%的资源需积分: 10 90 浏览量更新于2024-07-22 收藏 1.42MB PDF 举报

"《博弈论在无线工程师中的应用》是一本由Allen B. MacKenzie和Luiz A. DaSilva合著的著作，专为无线通信领域的专业人士设计。该书深入探讨了博弈论这一数学工具如何在无线通信和网络系统中发挥作用，尤其是在处理复杂动态环境中的问题，如移动性、流量模型、动态拓扑和不可预测的链路质量。书中首先介绍了博弈论的基本概念，包括正常形式博弈、重复博弈和马尔可夫博弈，通过文献中的实例进行阐述。作者强调了博弈理论如何模拟个体决策者的行为，这些决策者可能对其他决策者产生影响，这对于分析自组织（adhoc）网络的性能至关重要。早期到20世纪90年代，博弈论已经在网络控制（如流控、拥塞控制）、路由算法以及互联网服务定价等领域得到了应用。近年来，随着认知无线电等新兴技术的发展，博弈论在无线和对等网络中的资源分配、功率控制等方面展现了更大的潜力。书中还涉及如何在博弈论中引入学习机制，这与认知无线网络的学习能力密切相关。然而，应用博弈论分析无线系统的挑战和局限性也得到了讨论，包括如何处理不确定性和非合作行为。作者力求让读者在阅读本书后，对博弈论在无线通信和网络中的基础研究有深入的理解，包括介质访问控制、路由策略、能源效率协议等。《博弈论for Wireless Engineers》不仅是理论研究的基石，也为解决实际无线通信问题提供了实用的分析框架。该书是Morgan & Claypool出版社Synthesis Lectures on Communications系列的一部分，旨在为无线通信工程师提供一个全面而深入的理论指导，帮助他们理解并利用博弈论优化网络设计和性能。无论读者是否对博弈论有所了解，都能从本书中受益匪浅。版权信息表明，未经许可，不得任何形式复制或传播本书的部分内容。"

P1: JYS

MOBK014-01 MOBK014-MacKenzie-v1.cls February 20, 2006 17:35

4 GAME THEORY FOR WIRELESS ENGINEERS

Nonetheless, modern game theory usually traces its roots to the seminal Theory of Games

and Economic Behavior, by John von Neumann and Oskar Morgenstern, published in 1944.

Von Neumann and Morgenstern gave an axiomatic development of utility theory, which now

dominates economic thought and which we will explore in the next chapter, and also introduced

the formal notion of a cooperative game. Like much early work in game theory, though, their

work on noncooperative game theory (which now dominates the game theory literature) focused

on relatively simple two-person zero-sum games.

In papers between 1950 and 1953, John Nash contributed to the development of both

noncooperative and cooperative game theory [5–7]. His most important contribution, though,

was probably his existence proof of an equilibrium in noncooperative games, the Nash Equilib-

rium [5]; we will examine this proof in some detail in Chapter 3. For his contributions to game

theory, Nash shared in the 1994 Bank of Sweden Prize in Economic Sciences in Memory of

Alfred Nobel.

This early work was signiﬁcantly aided by work completed at the Rand Corporation,

which was formed after the World War II to connect military planning with research. With

this charter, the Rand Corporation sought to develop theories and tools for decision making

under uncertainty, leading to important contributions not only in game theory but also in

linear and dynamic programming and mathematical modeling and simulation. One of the early

applications of this theory was the study of the decision making of nations during the cold

war [8].

Since many of the early game theorists were economists, it is not surprising, perhaps, that

game theory’s greatestsuccess hasbeen in revolutionizingthe ﬁeldof economics. Ideasdeveloped

in the context of game theory now pervade almost every aspect of economic thought: utility

theory, strategic use of information, cooperative and team games, the problem of coordination

between independent players, auction theory, and implementation of incentive mechanisms.

Game theory has also made signiﬁcant contributions to other disciplines, including po-

litical science, sociology, biology, and military strategy. In the next section, we will discuss why

we believe that game theory has the potential to make signiﬁcant contributions to the study of

wireless communications and networking.

1.3 WHY IS GAME THEORY RELEVANT TO WIRELESS

COMMUNICATIONS AND NETWORKING?

Ad hoc networks have occupied a preeminent place in the wireless communications and net-

working literature for the last several years. An ad hoc network is a self-conﬁguring, multihop

network in which there is no central authority. Thus, every aspect of the conﬁguration and

operation of an ad hoc network must be completely distributed. Furthermore, nodes in an ad

hoc network are often severely energy and power constrained. In emerging wireless networks,

P1: JYS

MOBK014-01 MOBK014-MacKenzie-v1.cls February 20, 2006 17:35

INTRODUCTION TO GAME THEORY 5

such as sensor networks, mesh networks, and pervasive computing systems, many of these same

features—decentralized operation, self conﬁguration, and power/energy awareness—are often

desirable.

Game theory, as we have seen, is the study of the interaction of autonomous agents. At

this point, it should be clear how game theory may be of help when analyzing modern wireless

networks. In a modern wireless network, each node running a distributed protocol must make

its own decisions (possibly relying on information from other nodes). These decisions may

be constrained by the rules or algorithms of a protocol, but ultimately each node will have

some leeway in setting parameters or changing the mode of operation. These nodes, then, are

autonomous agents, making decisions about transmit power, packet forwarding, backoff time,

and so on.

In making these decisions, what does the node seek to optimize? In some cases, nodes

may seek the “greater good” of the network as a whole. In other cases, nodes may behave

selﬁshly, looking out for only their own user’s interests. In a ﬁnal case, nodes may behave

maliciously, seeking to ruin network performance for other users. In the second and third

cases, the application of game theory may be straightforward, as game theory traditionally

analyzes situations in which player objectives are in conﬂict. In the ﬁrst case, node objectives

may be aligned (as all players seek the “greater good” of the network), but game theory may

still offer useful insights. Even when nodes have shared objectives, they will each have a unique

perspective on the current network state,leading to possible conﬂicts regarding the best course of

action.

1.4 HOW CAN I USE GAME THEORY PROPERLY?

There are many potential pitfalls on the road to the application of game theory to wireless

communications and networking. One of these pitfalls has already been mentioned—mistaking

a simple optimization problem for a game. As we have already discussed, a problem is only a

game if there are multiple agents involved in making decisions. In some cases, it may be that

artiﬁcially creating multiple agents to play a game is worthwhile; in many cases, though, one

would be better served by using an optimization algorithm or technique. So, if it is not clear

who the agents are, one should carefully consider whether or not the use of game theory is

warranted.

A second common mistake in applications of game theory is confusion between the

theories of cooperative and noncooperative games. In this book, we focus on noncooperative

games, which have been primary in the study of game theory for the last 25 years or so.

Noncooperative game theory assumes agents with distinct interests that interact through a

predeﬁned mechanism; it encompasses concepts such as normal and extensive form games,

incomplete information, Nash equilibrium, and forward and backward induction. There is

P1: JYS

MOBK014-01 MOBK014-MacKenzie-v1.cls February 20, 2006 17:35

6 GAME THEORY FOR WIRELESS ENGINEERS

also a substantial body of literature on cooperative games, in which players form coalitions

and negotiate via an unspeciﬁed mechanism to allocate resources. Cooperative game theory

encompasses concepts such as the Nash bargaining solution and the Shapely value. Although

there are certainly proﬁtable applications of both theories and deep connections between the

two, the amateur game theorist would be well advised to mix the two theories with extreme

caution. Mixing the two theories can easily lead to results that are incomprehensible, at best,

and utter nonsense, at worst.

Perhaps the mostcommon mistake among legitimate applications ofgame theory, though,

is a failure to clearly deﬁne the game and the setting in which it is played. Who are the players of

the game? What actions are available to the players? What are the players’ objectives? Does an

equilibrium exist for the given game? Is it unique? Is there a dynamic process by which players

update their strategies? If so, what is it and is it guaranteed to converge?

Finally, there are two general “philosophies” on applying game theory, and it is extremely

important to consider which philosophy you are using. In many cases, researchers who have not

clearly thought through their reasoning will jump back and forth between the two philosophies.

This is bound to create holes in their arguments, as the philosophies are mutually exclusive.

The ﬁrst philosophy might be called a direct application of game theory. In this philoso-

phy, the users’ actual preferences are said to be modeled by the players’ utility functions. What

makes the application of this philosophy difﬁcult is that it is very difﬁcult to extract preferences

from users. Furthermore, nailing down a single explicit utility function that represents the

preferences of all users is not possible, since different users will have different preferences. It is

unlikely that even a parameterized utility function can represent the preferences of every user

except in very simple (perhaps contrived) situations. Even if one could postulate the existence

of such a function, it would take considerable effort to prove that such a formulation was valid

for the majority of users in the system.

Thus, if one wants to claim that the utility functions in a game represent actual users’

preferences, then one must operate with a bare minimum collection of assumptions about the

users’ preferences. Typical assumptions might include an assumption that users prefer higher

signal-to-interference-and-noise ratios (SINRs) to lower SINRs and that users prefer to spend

less power rather than more to obtain a given SINR. This approach can produce beautiful

results. It is, however, a very challenging task to execute well.

The second philosophy might be called an “engineering” application of game theory.

This philosophy assumes that the engineer is capable of programming the devices in the system

to behave as if they are maximizing a chosen utility function. Since the engineer chooses the

utility function, it can be whatever the engineer desires. The burden in this philosophy lies

in explaining why a particular utility function has been chosen and why game theory is being

employed at all. Though perhaps easier than demonstrating that a particular utility function

represents the preferences of all users, this may still be a difﬁcult challenge to meet.

P1: JYS

MOBK014-01 MOBK014-MacKenzie-v1.cls February 20, 2006 17:35

INTRODUCTION TO GAME THEORY 7

Note that there is a stark contrast between these two philosophies. Either you are claiming

thatyour utility functionsrepresentactual userpreferences—inwhichcase youhadbetter provide

some evidence or make the assumptions about those functions very light—or you are not—in

which case you had better provide some other compelling reason for using game theory.

The pointof thissection is notto discouragethe use ofgame theory. Obviously,the authors

think that game theory is a valuable tool for approaching a number of different problems; as

discussed before, game theory has revolutionized economics. The point, though, is that game

theory, like any tool, must be used carefully and on the right kind of problems. To quote a

familiar clich

e, “If the only tool you have is a hammer, then every problem looks like a nail.”

We must be vigilant not to fall into that trap.

1.5 INTRODUCTION TO EXAMPLES

In this work, we will discuss a variety of communications and networking examples to illustrate

the concepts that we introduce. These examples should provide a sense of how game theory

has been used by researchers and will hopefully inspire you to consider some of your own game

theory applications. The examples should also demonstrate (on a small scale) each of the two

philosophies discussed above.

This section brieﬂy introduces three examples to start your thinking along game theoretic

lines.

1.5.1 Power Control

The problem of uplink power control in a code division multiple access (CDMA) cellular system

has been considered by a number of authors [9–14]. For simplicity, we will discuss a single-cell

model, although multi-cell models (and, more recently, even ad hoc models) are also discussed

in the literature.

The players in a cellular power control game are the cellular telephones in the cell. This

is often assumed to be a ﬁxed, known number of players. Each player’s action is the power level

that she chooses. In many cases, this is limited to be a power level between 0 and p

max

, although

some games consider power levels between 0 and ∞.

The question of payoff functions, as usual, is the most difﬁcult question; we will consider

it further in the next chapter. For now, though, consider the following properties, which make

this problem appropriate for a game model.

•

The player’s payoff is a function of her own transmit power level and her SINR. The

player’s SINR is a function of her own transmit power and the transmit powers of the

other players in the cell.

•

When a player increases her power level, this will increase her own SINR, but will

decrease the SINRs of all other players.

P1: JYS

MOBK014-01 MOBK014-MacKenzie-v1.cls February 20, 2006 17:35

8 GAME THEORY FOR WIRELESS ENGINEERS

•

For a ﬁxed SINR, the players prefer lower power levels to higher ones. That is, players

wish to conserve power and extend their battery life when possible.

•

For a ﬁxed power level, players prefer higher SINR to lower SINR. That is, players

want the best possible channel conditions for a given expenditure of power.

Game theoretic analysis of this situation has yielded several conclusions. First, taken as

a simple game, the power control situation described here usually leads to extremely inefﬁcient

outcomes. What typically occurs is that each player increases her power to increase her SINR.

This power increase, though, decreases the SINRs of other users, who then increase their power

levels to compensate. By the time an equilibrium is reached, all users are blasting away at much

higher power levels than necessary—they could all reduce their powers and everyone would be

better off. This could perhaps be viewed as a negative result for game theory, but we believe

that it provides some insight into the reality of power control: left to their own devices, selﬁsh

users will behave inefﬁciently in the power control game.

Second, though, game theory provides some insight into ways to obtain better outcomes

in the power control scenario. For instance, it is possible to add external incentives against

power increases, such as charging users based on transmit power. Another option is to model

the scenario as a repeated game, where users can punish each other for using too much power.

We will look at some of these possibilities in a future chapter.

What makes this problem interesting to model as a game? There are multiple nodes

making individual power control decisions that impact the performance of every node in the

cell. Thus, we have an interactive decision problem of the type that is well modeled by game

theory.

1.5.2 Routing

Another problem that is well modeled by game theory is the problem of routing in a network.

Some examples of work in this area include [15–18]. For simplicity, we assume that a policy

of source routing is followed, where the complete route for each packet is determined by the

packet source.

In this problem, the players in the game could be viewed as the source nodes in the

network, but it is slightly more convenient to view a player as a source/destination pair.

(In reality, the decision making will be carried out by the source, but making the source/

destination pair the player allows for the existence of multiple ﬂows from a single source.) The

action set available to each player is the set of all possible paths from the source to the destina-

tion. (In many formulations of the routing game, nodes can actually choose multiple routes and

decide how much of their ﬂow to send on each route. We ignore this complication for now.)

剩余85页未读，继续阅读

WNeverBelieve

粉丝: 0
资源: 4

博弈论在无线通信工程中的应用与挑战

博弈论在无线通信中的应用

博弈论在无线工程中的应用

《Ada for Software Engineers》：编程语言与工程实践指南

Advanced Probability Theory for Biomedical Engineers - John D. Enderle

Electromagnetic Theory and Plasmonics for Engineers.rar

Plasticity for Structural Engineers

JUNOS FOR IOS ENGINEERS

fortran_for_engineers

reference data for radio engineers

Ada for Software Engineers.pdf

最新资源