Koster A., Munoz X. Graphs and Algorithms in Communication Networks

Подождите немного. Документ загружается.

11 Mathematical Optimization Models for WLAN Planning 303

1 700

]

500

(a) Reference solution

1 700

]

500

(b) M

TAL solution with 3-MOCA channel assignment: APs with large

pairwise overlap are assigned different channels

1 700

]

500

T-MO solution (

= 0.6): the AP positioning has very little

overlap to begin with, and the channel assignment further reduces it

Fig. 11.7 Overlap graph and channel assignment

304 S. Bosio et al.

(a) Channel assignment for minimum

overlap

(b) Channel assignment for maximum

efﬁciency: a slight change enables

higher efﬁciency in the service areas of

some APs

0.22

[Mbit/s]

0.00

Fig. 11.8 Channel assignment by optimizing overlap vs. efﬁciency, evaluated in the latter metric

(APs are positioned for maximum throughput)

(a) Reference conﬁguration: many test

points have low efﬁciency

(b) Integrated optimization makes for bet-

ter efﬁciency

0.22

[Mbit/s]

0.00

Fig. 11.9 Effect of integrated optimization on efﬁciency

The experiments are organized as follows. First, model MTAL is applied to ﬁnd

a solution of AP location that maximizes the single-user throughput. Then channel

assignment is performed, with both the minimum-overlap approach (3-M

OCA) and

the maximum-efﬁciency approach (3-M

ECA). Finally, we illustrate integrated AP

location and channel assignment by model 3-M

T-MO.

Model M

TAL is implemented using ZIMPL [22] and solved with ILOG CPLEX

10.0 [35]. The computational time is a few seconds. The single-user throughput of

the optimal solution to M

TAL is shown in Figure 11.6(b). It is possible to observe

that each AP in this solution serves some areas on both ﬂoors, while in the reference

solution the service area of each AP is mostly limited to the ﬂoor where the AP is

installed. The total coverage loss in the optimized solution is only 1.71%. There is

a signiﬁcant improvement in the single-user throughput distribution in comparison

to the reference solution. The average throughput is 23.11% higher, and the size of

areas that either are not covered or suffer from low throughput (below 1 Mbit/s) is

reduced by a factor of 3.5.

11 Mathematical Optimization Models for WLAN Planning 305

Table 11.1 Performance evaluation of the optimization results. For each network plan we eval-

uate the single-user throughput, the co-channel overlap, the pairwise co-channel overlap (M

OCA

objective function), and the network efﬁciency (MECA objective function)

Model

Throughput Overlap Pairwise overlap Efﬁciency

[Mbit/s] [%] (M

OCA)(MECA)

Reference solution 10.69 48.93 14.38 89.55

TAL +3-MOCA 13.16 37.55 7.03 96.93

TAL +3-MECA 13.16 44.08 7.39 102.82

3-M

T-MO,

= 0.1, 0.2 13.16 31.56 2.11 103.13

3-M

T-MO,

= 0.3, 0.4,0.5 13.10 21.41 1.39 107.17

3-M

T-MO,

= 0.6, 0.7 13.06 20.59 1.23 106.09

3-M

T-MO,

= 0.8 12.66 18.30 0.95 110.98

3-M

T-MO,

= 0.9 12.41 18.37 0.87 108.68

3-M

T-MO,

= 1.0 12.19 24.06 0.87 104.08

The next step is channel assignment. In Figure 11.7(b) we show the channel as-

signment obtained by solving model 3-M

OCA, reporting its overlap graph (which is

optimal for the given AP location), and in Figure 11.8(a) its evaluation in terms of

the efﬁciency metric. For this network instance model, 3-M

OCA can be solved very

rapidly (in less than one second). Comparing the overlap graph of this solution with

that of the reference solution (Figure 11.7(a)), it is easy to see that the former con-

tains fewer links with high overlap. The improvement upon the reference solution

in the average efﬁciency is 6.29%, although much of this improvement is due to the

higher single-user throughput of the AP location obtained with model M

TAL.

Figure 11.8(b) reports the efﬁciency metric evaluation for the channel assignment

obtained by solving model 3-M

ECA. The model can be solved for this instance in

a few seconds. The improvement in efﬁciency with respect to the channel assign-

ment obtained with 3-M

OCA is 6.07%, with an increase in overlap of 5.08%. The

improvement in efﬁciency with respect to the reference solution is 12.75%.

We end the presentation of computational experiments by considering integrated

AP location and channel assignment using model 3-M

T-MO.Welet

vary in the

interval (0,1) with step size 0.1. Small values of

emphasize throughput maximiza-

tion, while values close to 1.0 put more weight on overlap minimization. Note also

that for a sufﬁciently small value of

the problem becomes equivalent to solving

TAL and 3-MOCA in two sequential steps.

In Table 11.1 we compare the reference solution to the results obtained from the

models M

TAL,3-MOCA,3-MECA, as well as from the combined model 3-MT-MO.

The throughput column shows the single-user throughput averaged over the TPs that

are within the serving range of at least one AP. The overlap performance metric is

the fraction (in %) of the total area where the serving AP overlaps with at least one

other AP from which the received signal is above the carrier sense threshold. Note

that the latter is a performance evaluation metric and has not been taken into account

explicitly in the optimization models. The last two columns show values of the two

objective functions (M

OCA and MECA) for each of the solutions.

306 S. Bosio et al.

From Table 11.1, we observe that, as for two-step optimization, the solution of

the integrated model 3-M

T-MO outperforms the reference solution for all values of

. The improvement in throughput declines when

grows, but the degradation is

signiﬁcant only if

is very close to 1. Up to

= 0.7, throughput is hardly sacriﬁced

when pursuing the goal of reducing overlap. The improvement over the two-step op-

timization is signiﬁcant. The loss in throughput is very small, while the gain in both

overlap and efﬁciency (even if 3-M

T-MO is not designed to optimize efﬁciency) is

remarkable, as it can be appreciated from Figure 11.9. This observation supports ap-

plying the integrated optimization to WLAN planning, whenever the computational

complexity required can be afforded, and using the two-step optimization when a

lower computational effort is required.

From Table 11.1 we conclude that

= 0.6 appears as a good trade-off between

the two objectives. The single-user throughput for the corresponding solution is

shown in Figure 11.6(c), while the overlap map and the efﬁciency evaluation are

shown respectively in Figures 11.7(c) and 11.9(b).

11.10 Conclusions and Perspectives

Designing wireless LANs for seamless coverage and high capacity in large ofﬁce

buildings is a challenge. On the one hand, good coverage and high throughput ide-

ally call for a high density of APs. On the other hand, the availability of only three

non-overlapping channels (out of 13 in total) suggests placing APs far apart. Other

constraints and considerations, such as that APs typically need a wired network con-

nection and that they should not be too easily accessible to prevent manipulation or

damage, further complicate the planning task.

The challenge has been addressed in this chapter by means of mathematical opti-

mization. The two aspects, providing coverage and controlling interference, can be

addressed either in a two-step approach solving AP location and channel assignment

separately, or with an integrated approach. These approaches have been compared in

a real-life planning scenario for two adjacent ﬂoors of an ofﬁce building. The man-

ual design of the network, used as a reference, employs the same AP location pattern

on both ﬂoors. Interference is limited by using four, partially overlapping channels.

The optimized solutions clearly reveal a strong dependency among the AP locations

and channel assignments across the two ﬂoors. Moreover, optimization signiﬁcantly

improves the coverage.

Comparing the optimization results with respect to the overlap of AP service

areas using the same channel, solutions from the combined model are superior to

those from the two-step approach. The difference, however, is not large enough to

clearly justify the use of the much larger and more complex combined model. An

appropriate trade-off between network performance and problem tractability must

therefore be decided according to the needs and will change from case to case.

The network efﬁciency measure, which aggregates throughput and overlap, turns

out to be quite consistent with the pairwise overlap measure in terms of the result-

11 Mathematical Optimization Models for WLAN Planning 307

ing networks. Indeed, the channel assignment of the solutions obtained from the

combined model for alpha greater than or equal to 0.3 are optimal for the network

efﬁciency measure. A more precise comparison of the networks resulting from these

alternative objective functions would, however, require us to consider more network

performance parameters.

AP service area overlap is used as a measure of interference in some of the chan-

nel assignment models. The actual interference situation cannot be properly com-

pared on the basis of the mathematical models presented here. In fact, the effects of

using overlapping channels in the reference design need to be assessed in a detailed

simulation study, which is beyond the scope of this chapter.

In case overlapping channels can safely be deployed under sufﬁciently general

conditions, the presented models are applicable, although at a higher computational

price. When increasing the number of channels from three to as many as 13, spe-

cialized solution methods as well as heuristics are likely to be more successful than

the plain application of an MIP solver.

Acknowledgements The research reported in this chapter has been conducted in two short-term

scientiﬁc missions (STSMs) of EU COST action 293 – Graphs and Algorithms in Communication

Networks (GRAAL). The work of the last author is supported by CENIIT, Link

oping University,

Sweden.

References

1. Aardal, K. I., Hoesel, C. P. M. v., Koster, A. M. C. A., Mannino, C., Sassano, A.: Models

and solution techniques for frequency assignment problems. Annals of Operations Research

153(1), 79–129 (2007)

2. Aardal, K. I., Hurkens, C., Lenstra, J. K., Tiourine, S.: Algorithms for the radio link frequency

assignment problem: The CALMA project. Operations Research 50, 968–980 (2002)

3. Abusubaih, M., Gross, J., Wiethoelter, S., Wolisz, A.: On access point selection in IEEE

802.11 wireless local area networks. In: Proc. of the Sixth International Workshop on Wireless

Local Networks (WLN 2006) (2006)

4. Amaldi, E., Bosio, S., Malucelli, F., Yuan, D.: On a new class of set covering problems arising

in WLAN design. In: Proc. of the Intl. Network Optimization Conference (INOC ’05), pp.

470–478 (2005)

5. Amaldi, E., Capone, A., Cesana, M., Malucelli, F.: Optimizing WLAN radio coverage. In:

Proc. of the 2004 IEEE International Conference on Communications, vol. 1, pp. 180–184

(2004)

6. Bosio, S., Capone, A., Cesana, M.: Radio planning of Wireless Local Area Networks.

IEEE/ACM Transactions on Networking 15(6), 1414–1427 (2007)

7. Cisco Systems, Inc., http://www.cisco.com/en/US/products/hw/wireless/

ps430/: Cisco Aironet 1200 Series Access Points, Data sheet

8. Cisco Systems, Inc.: Channel deployment issues for 2.4-GHz 802.11 WLANs. Tech. rep.,

http://www.cisco.com/ (2004)

9. Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer (2005)

10. Eisenbl

atter, A.: Frequency assignment in GSM networks: Models, heuristics, and lower

bounds. Ph.D. thesis, Technische Universit

at Berlin, Berlin, Germany (2001)

11. Eisenbl

atter, A., Geerdes, H. F., Siomina, I.: Integrated access point placement and channel

assignment for Wireless LANs in an indoor ofﬁce environment. In: Proc. of the 8th IEEE Intl.

308 S. Bosio et al.

Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM 2007)

(2007)

12. Eisenbl

atter, A., Gr

otschel, M., Koster, A. M. C. A.: Frequency planning and ramiﬁcations of

coloring. Discussiones Mathematicae Graph Theory 22(1), 51–88 (2002)

13. Hansen, P., de Arag

ao, M. V. P., Ribeiro, C. C.: Boolean query optimization and the 0-1 hy-

perbolic sum problem. Annals of Mathematics and Artiﬁcial Intelligence 1, 97–109 (1990)

14. Hills, A.: Large-scale wireless LAN design. IEEE Communications Magazine 39(11), 98–107

(2001)

15. Hills, A., Friday, B.: Radio resource management in wireless LANs. IEEE Radio Communi-

cations Magazine 42(12), S9–14 (2004)

16. IEEE Standards Association: IEEE Std 802.11-2007.

http://standards.ieee.org/getieee802/802.11.html (2007)

17. Jaffr

es-Runser, K., Gorce, J. M., Ub

eda, S.: QoS constrained wireless LAN optimization

within a multiobjective framework. IEEE Wireless Communications 13(6), 26–33 (2006)

18. Jeavons, P., Dunkin, N., Bater, J.: Why higher order constraints are necessary to model fre-

quency assignment problems. In: ECAI’98 Workshop on Non-binary constraints (1998)

19. Jemai, J., Piesiewicz, R., K

urner, T.: Calibration of an indoor radio propagation prediction

model at 2.4 GHz by measurements of the IEEE 802.11b preamble (2002). COST 273 TD,

Duisburg, Germany

20. Jemai, J., Reimers, U.: Channel modeling for in-home wireless networks. In: Proc. of IEEE

Intl. Symposium on Consumer Electronics (ISCE02), pp. F123–F129. Erfurt, Germany (2002)

21. Kamenetsky, M., Unbehaun, M.: Coverage planning for outdoor wireless LAN. In: Proc. of

Intl. Zurich Seminar on Broadband Communications, 2002. Access, Transmission, Network-

ing (IZS). Zurich, Switzerland (2002)

22. Koch, T.: Rapid mathematical programming. Ph.D. thesis, TU Berlin, Germany (2004). Avail-

able at http://www.zib.de/Publications/abstracts/ZR-04-58/,ZIMPLis

available at http://www.zib.de/koch/zimpl

23. Koster, A. M. C. A.: Frequency assignment – models and algorithms. Ph.D. thesis, Maastricht

University (1999)

24. Kumar, A., Kumar, V.: Optimal Association of Stations and APs in an IEEE 802.11 WLAN.

In: Proc. National Conference on Communications (NCC). India (2005)

25. Lee, Y., Kim, K., Choi, Y.: Optimization of AP placement and channel assignment in wireless

LANs. In: Proc. of the 27th Annual IEEE Conference on Local Computer Networks (LCN’02)

(2002)

26. Leung, K. K., Kim, B. J.: Frequency assignment for IEEE 802.11 wireless networks. In: Proc.

of the 58th IEEE Vehicular Technology Conference (VTC2003-Fall). Orlando, FL (2003)

27. Ling, X., Yeung, K. L.: Joint access point placement and channel assignment for 802.11 wire-

less LANs. In: Proc. of IEEE Wireless Communications and Networking Conference (WCNC

2005). New Orleans, LA (2005)

28. Mateus, G. R., Loureiro, A. A. F., Rodrigues, R. C.: Optimal network design for wireless local

area network. Annals of Operations Research 106(331-345) (2001)

29. Mishra, A., Banerjee, S., Arbaugh, W.: Weighted coloring based channel assignment for

WLANs. ACM SIGMOBILE Mobile Computing and Communications Review 9(3), 19–31

(2005)

30. Prommak, C., Kabara, J., Tipper, D., Charnsripinyo, C.: Next generation wireless LAN system

design. In: Proc. of the IEEE Military Conference (MILCOM 2002), vol. 1, pp. 473–477

(2002)

31. Riihij

arvi, J., Petrova, M., M

onen, P.: Frequency allocation for WLANs using graph colour-

ing techniques. In: Proc. of the Second Annual Conference on Wireless On-Demand Network

Systemsand Services (WONS ’05). St. Moritz, Switzerland (2005)

32. Sherali, H. D., Pendyala, C. M., Rappaport, T. S.: Optimal location of transmitters for micro-

cellular radio communication system design. IEEE Journal on Selected Areas in Communi-

cations 14(4), 662–673 (1996)

33. Siomina, I.: Wireless LANs planning and optimization. STSM Technical Report, COST Ac-

tion TIST 293 (2005)

11 Mathematical Optimization Models for WLAN Planning 309

34. Siomina, I., Yuan, D.: Optimization of channel assignment and access point transmit power for

minimizing contention in Wireless LANs. In: Proc. of the 5th Intl. Symposium on Modeling

and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt 2007) (2007)

35. ILOG, Inc: ILOG CPLEX 10.0, User’s manual (2006)

36. Unbehaun, M., Kamenetky, M.: On the deployment of picocellular wireless infrastructure.

IEEE Wireless Communications 10 (2003)

37. Villegas, E. G., Ferr

e, R. V., Aspas, J. P.: Implementation of a distributed dynamic channel

assignment mechanism for IEEE 802.11 networks. In: Proc. of the 16th IEEE International

Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2005), vol. 3,

pp. 1458–1462 (2005)

38. Villegas, E. G., L

opez-Aguilera, E., Ferr

e, R. V., Aspas, J. P.: Effect of adjacent-channel in-

terference in IEEE 802.11 WLANs. In: Proc. of the 2nd Intl. Conference on Cognitive Radio

Oriented Wireless Networks and Communications (CrownCom ’07) (2007)

39. Wertz, P., Sauter, M., W

olﬂe, G., Hoppe, R., Landstorfer, F. M.: Automatic optimization algo-

rithms for the planning of wireless local area networks. In: Proc. of the 60th IEEE Vehicular

Technology Conference (VTC2004-Fall). Los Angeles, CA (2004)

40. Zdarsky, F. A., Martinovic, I., Schmitt, J. B.: On lower bounds for MAC layer contention in

CSMA/CA-based wireless networks. In: Proc. of Workshop on Discrete Algothrithms and

Methods for MOBILE Computing and Communications (DIALM’05), pp. 8–16. Cologne,

Germany (2005)

Chapter 12

Time-Efﬁcient Broadcast in Radio Networks

David Peleg and Tomasz Radzik

Abstract Broadcasting is a basic network communication task, where a message

initially held by a source node has to be disseminated to all other nodes in the net-

work. Fast algorithms for broadcasting in radio networks have been studied in a wide

variety of different models and under different requirements. Some of the main pa-

rameters giving rise to the different variants of the problem are the accessibility of

knowledge about the network topology, the availability of collision detection mech-

anisms, the wake-up mode, the topology classes considered, and the use of random-

ness. This chapter introduces the problem, reviews the literature on time-efﬁcient

broadcasting algorithms for radio networks under a variety of models and assump-

tions, and illustrates some of the basic techniques.

Key words: radio networks, broadcasting, broadcasting sequence, selective fami-

lies, unit disk graphs

12.1 Introduction

12.1.1 The Problem

A radio network consists of nodes, each equipped with a device enabling it to trans-

mit and receive messages. At any given time, each node decides whether to act as

a transmitter or as a receiver. Reception conditions are modeled by a network con-

David Peleg

Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science,

Rehovot, Israel, e-mail: david.peleg@weizmann.ac.il

Tomasz Radzik

Department of Computer Science, King’s College London, London WC2R 2LS, United Kingdom,

e-mail: tomasz.radzik@kcl.ac.uk

A.M.C.A. Koster, X. Mu

noz (eds.), Graphs and Algorithms in Communication 311

Networks, Texts in Theoretical Computer Science. An EATCS Series,

DOI 10.1007/978-3-642-02250-0

12,

 Springer-Verlag Berlin Heidelberg 2010

312 D. Peleg, T. Radzik

necting the nodes, where the existence of a (directed) edge from a node v to a node

u indicates that transmissions of v can reach u directly.

A node acting as a transmitter in a given time step transmits a message that

reaches all of its outgoing neighbors in the network in the same time step. However,

its being within range of a transmitting node does not necessarily ensure that its

transmitted message is received successfully. A node acting as a receiver in a given

step successfully hears a message if and only if exactly one of its incoming neigh-

bors transmits in this step. If two or more incoming neighbors v and v



of u transmit

simultaneously in a given step, then neither of their messages is heard by u.Inthis

case we say that a collision occurred at u.

This chapter considers broadcasting in radio networks, which is the following ba-

sic communication task. Initially, one distinguished node s, called the source, has a

message M that has to be delivered to all other nodes in the network. Remote nodes,

which cannot receive the transmissions of s directly, have to get M via intermediate

nodes.

The model considered in most of the literature on broadcasting algorithms in

radio networks is synchronous. All nodes have individual clocks that tick at the

same rate, measuring time steps, also referred to as rounds. Any execution of a

broadcasting operation can be described as a sequence T

,...,T

, hereafter referred

to as a broadcasting sequence, where each T

is a transmission set consisting of the

nodes that acted as transmitters in time step i. The execution time of a broadcasting

algorithm in a given radio network is the number of rounds it takes since the ﬁrst

transmission until all nodes of the network hear the source message, or in other

words, the length of the corresponding broadcast sequence.

The current chapter reviews the literature on time-efﬁcient broadcasting algo-

rithms for radio networks under a variety of models and assumptions.

The question of time-efﬁcient broadcasting has been examined from two related

but distinct viewpoints. The ﬁrst, more mathematical, viewpoint concerns investi-

gating the absolute optimum time required for broadcasting. For a radio network G,

let b(G) denote the length of the shortest possible execution of the broadcasting op-

eration for G. The study of broadcasting time from this viewpoint concentrated on

the abstract question of identifying or tightly bounding the function b, and thus fo-

cused on establishing the existence or nonexistence of short broadcasting sequences

for a given network, using a variety of algorithmic, probabilistic, and nonconstruc-

tive methods.

To bound the function b(G), it was necessary to identify the graph-theoretic

parameters governing its behavior. Clearly, the radius of a network G from the

source s, denoted R(G,s) (i.e., the largest distance between s and any other node

in G), serves as a lower bound for the length of any broadcasting sequence on G.

For uniformity over the different sources, we use the network diameter D (i.e., the

largest distance between any two nodes in G) instead. (Note that D/2 ≤R(G,s) ≤D

for every node s in G.) It also stands to reason that n, the number of nodes in

the network, plays a role in the cost of broadcasting. Consequently, let us deﬁne

b(n,D)=maxb(G), where the maximum is taken over all radio networks G of n

12 Time-Efﬁcient Broadcast in Radio Networks 313

nodes and diameter D. The mathematical problem stated above now becomes iden-

tifying the function

b(n,D).

The second viewpoint deals with the more algorithmic question of developing

protocols for time-efﬁcient broadcasting in realistic settings. This question can be

studied in a variety of models. To begin, one may consider a centralized setting. In

this setting, we assume that the graph topology is known in advance, and the goal

is to design, in an off-line preprocessing stage, an optimal (time-minimal) or near-

optimal solution for the broadcasting problem. Such a solution can sometimes be

represented in the form of a ﬁxed schedule, which essentially describes the optimal

execution, i.e., speciﬁes a broadcasting sequence T

,...,T

. The schedule can be

applied as a broadcast procedure in the natural way: In step i, every node v ∈ T

which already holds a copy of the source message M transmits it. A node v ∈ T

that

does not have a copy yet remains silent. The schedule S is a broadcast schedule for

the source s in G if after applying it, every node in the network has a copy of M.

While the question of determining the minimum length of broadcasting sched-

ules for radio networks is very basic and of considerable theoretical interest, in

reality such schedules are hardly ever used, for a variety of practical reasons. For in-

stance, such centrally computed ﬁxed schedules are only useful when the network is

relatively stable; in dynamic environments, where the network topology constantly

changes, such schedules are hard to construct, maintain, and update.

The common practice is therefore to employ distributed broadcasting protocols,

which generate the broadcasting sequence “on the ﬂy,” while performing the broad-

casting operation itself. This approach has obvious advantages in terms of simplicity

and ﬂexibility. On the down side, the typical situation in the distributed context is

that nodes are unaware of the topology of the network and have limited or no knowl-

edge of other parameters of the network, such as its diameter or size. They may not

even be aware of their immediate neighborhood, namely, the identity of their neigh-

bors. Networks in which the nodes have such limited knowledge are often called ad

hoc networks. This lack of centralized knowledge rules out the efﬁcient design of

optimal or even near-optimal execution sequences. In fact, distributed broadcasting

algorithms that rely on partial knowledge of the topology must usually involve trial-

and-error, possibly incurring wasteful (but unavoidable) collisions, and are generally

expected to generate signiﬁcantly slower broadcasting sequences. Hence the focus

in this area is on developing efﬁcient algorithms that quickly adapt to the network

at hand, possibly through learning its topology or some of its properties, and man-

age to tailor a relatively short execution sequence for it. Let

(n,D) (respectively,

(n,D)) denote the time required for broadcasting on an n-node radio network of

diameter D by a distributed deterministic (or randomized) algorithm. (Clearly, this

function depends on the precise model and class of networks under consideration.)

Interestingly, despite the obvious advantages of adaptivity, which advocate the

use of fully distributed, local, online, and dynamically adapting solutions, in some

cases the best algorithms currently known are essentially oblivious, in the sense that

the actions taken by each node depend only on its identity and the current time

step, but not on the history of the execution. Such algorithms can be thought of as

requiring the nodes to follow ﬁxed precomputed schedules, designed by a central