비영리 - S-Space - 서울대학교

(1)

저작자표시-비영리-변경금지 2.0 대한민국 이용자는 아래의 조건을 따르는 경우에 한하여 자유롭게

l 이 저작물을 복제, 배포, 전송, 전시, 공연 및 방송할 수 있습니다. 다음과 같은 조건을 따라야 합니다:

l 귀하는, 이 저작물의 재이용이나 배포의 경우, 이 저작물에 적용된 이용허락조건 을 명확하게 나타내어야 합니다.

저작권법에 따른 이용자의 권리는 위의 내용에 의하여 영향을 받지 않습니다. 이것은 이용허락규약(Legal Code)을 이해하기 쉽게 요약한 것입니다.

Disclaimer

저작자표시. 귀하는 원저작자를 표시하여야 합니다.

비영리. 귀하는 이 저작물을 영리 목적으로 이용할 수 없습니다.

변경금지. 귀하는 이 저작물을 개작, 변형 또는 가공할 수 없습니다.

(2)

M.S. THESIS

Anti-Starvation Channel Allocation Algorithm in Dense 802.11 Networks

고밀도 802.11 네트워크를 위한 기아 방지 채널 할당

알고리즘

BY

DONGHYUK GWAK 곽 동 혁

FEBRUARY 2013

DEPARTMENT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

COLLEGE OF ENGINEERING

(3)

M.S. THESIS

알고리즘

BY

DONGHYUK GWAK 곽 동 혁

FEBRUARY 2013

DEPARTMENT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

COLLEGE OF ENGINEERING

(4)

알고리즘

지도교수 이 광 복

이 논문을 공학석사 학위논문으로 제출함

2013 년 2 월

서울대학교 대학원

전기 컴퓨터 공학부

곽 동 혁

곽동혁의 공학석사 학위논문을 인준함

2013 년 2 월

위 원 장 박세웅

(5)

Abstract

DONGHYUK GWAK DEPARTMENT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE COLLEGE OF ENGINEERING SEOUL NATIONAL UNIVERSITY

Abstract - Since density of 802.11 devices has shown fast increase, starvation has become serious problem for 802.11 networks. Although there are several existing channel allocation algorithms for 802.11 networks, these algorithms still have difficulty in dealing with starvation problems. To improve user experience in dense environment, solution of starvation problem is essential. In this paper, we propose a new channel allocation algorithm which is able to relieve starvation problem efficiently. While LCCS and Hminmax set their main purpose as sum throughput maximization, this new algorithm has its aim on relieving nodes suffering from starvation. This new algorithm reduces the occurrence of the two types of starvation, carrier sense starvation and hidden node starvation,

(6)

and improves the system fairness.

Keywords: Wireless LAN, 802.11, Channel Allocation, Anti-Starvation, Fair- ness Enhancement

Student Number: 2010-23242

(7)

2.1 802.11 Orthogonal Channel Set . . . 3 2.2 Previous Works on Channel Assignment of 802.11 System . . . . 4 2.3 Carrier Sense Starvation Problem . . . 4 2.4 Hidden Node Problem . . . 5 Chapter 3 System Model and Proposed Algorithm 6 3.1 Notation conventions . . . 6 3.2 Problem Formulation . . . 7 3.3 Proposed Algorithm . . . 8

(8)

Chapter 4 Simulation Results 11

Chapter 5 Conclusion 20

Bibliography 21

Abstract in Korean 23

Acknowledgements 24

(9)

List of Figures

Figure 3.1 Notation conventions . . . 7

Figure 3.2 Flowchart . . . 9

Figure 3.3 Pseudocode of proposed algorithm . . . 10

Figure 3.4 Objective function of proposed algorithm . . . 10

Figure 4.1 Simulation environments . . . 11

Figure 4.2 Topology of situation 1 . . . 12

Figure 4.3 Goodput bar graph of situation 1 . . . 16

(10)

List of Tables

Table 4.1 Throughput and fairness comparison . . . 19

(11)

Chapter 1

Introduction

Owing to great success in industry, the density of 802.11 devices is getting higher. As the density increases, inter-802.11 interference also increases. Many channel allocation algorithms[1, 2, 5] have been devised to reduce these inter- 802.11 interference. Though existing channel allocation algorithms reduced inter- cell interference and brought improvement of sum throughput, those algorithms have possibility of letting devices suffer from starvation problems. In high density region, starvation can be main source of poor user experience. So to resolve harm of starvation, we designed novel 802.11 channel allocation algorithm.

The proposed algorithm has several features. First, it allocates orthogonal channels to nodes in order to avoid adjacent channel interference (ACI). ACI cannot be recognized as busy state of channel by receiver, so its effect on other

(12)

link is similar to that of the hidden node problem. As hidden nodes possibly induce starvation problem, algorithm proposed in this paper does not use non orthogonal channels[3]. Second, this algorithm operates in centralized manner.

It is essential to obtain the information of the whole graph to avoid carrier sense starvation. By using this information, the node recognizes which two neighbor APs are hidden to each other. Third, the AP running this algorithm receives assistance of clients associated with it. The clients send list of APs in their carrier sense range to make the AP aware of hidden APs. The proposed algorithm in this paper tries to mitigate starvation problem by utilizing assistance of other nodes as told above.

The rest of this paper is organized as follows. In Chapter 2, background knowledge about existing algorithms and starvation problems are mentioned.

Chapter 3 describes about system modeling and problem formulation. Simula- tion results are presented in Chapter 4, and conclusions are drawn in Chapter 5.

(13)

Chapter 2

Background

2.1 802.11 Orthogonal Channel Set

802.11 defines its available channel set in its standards. For some standards like 802.11a/n, all channels defined in the standards are orthogonal to other channels. But for some other standards like 802.11b/g, there are 11 to 13 non- orthogonal channels available. For these standards, orthogonal channel set can be obtained by collecting channels which have enough frequency spacing from other channels. So in 802.11b/g, 4 orthogonal channels are available to follow ISM band regulation in South Korea. And for some other region only 3 orthogonal channels are available. The proposed algorithm allocates channels in orthogonal channel set only.

(14)

2.2 Previous Works on Channel Assignment of 802.11 System

Least congested channel search (LCCS)[1] is one of most prevailing channel selection algorithm for WLAN. A WLAN AP running this algorithm detects APs in its range. Then the AP finds out which channel have the fewest number of APs operating in its range. Then the AP makes decision to operate on that least congested channel. For its simple and implementable characteristics, LCCS is widely used for WLAN devices.

Hminmax and Hsum[5] are coloring algorithms using weighted graph. These algorithm uses graph with weighted edges and the weights are determined by interference power and attenuation factor of ACI. But these algorithms should be criticized for the reason that they treat ACI as attenuated co-channel interference. Actually, harm of ACI is more serious than that of attenuated co-channel interference[4].

2.3 Carrier Sense Starvation Problem

Carrier sense starvation occurs when a node has multiple neighbor nodes which cannot sense each other. The word ”neighbor nodes” refers to nodes that are in carrier sense range of the node, so that they are in contention relationship.

If the neighbor nodes are not aware of each other, then there is possibility that

(15)

observed air is busy for a prolonged time due to channel occupation of neighbor nodes. It makes the node have much less channel access opportunity then it should be.

2.4 Hidden Node Problem

The word ”hidden node” refers to a node that is not sensible by other nodes. For contention mechanism to work in proper way, transmitters in conflict should be in sensing range of each other. If receiver is in range of interfering node and transmitter is hidden in a view of interfering node, then hidden node problem occurs. Because hidden nodes transmit traffic without knowing whether other transmitters are transmitting or not, packets collide and performance degrada- tion occurs.

(16)

Chapter 3

System Model and Proposed Algorithm

In this section, we define system model and describe detailed operation of novel anti-starvation algorithm.

3.1 Notation conventions

Notations used in this paper are described in Figure 3.1. The sets U and V are set of APs and STAs each. And V_k is a set of STAs associated with u_k. Edges are used to express carrier sense relationship between two nodes, and they are expressed as pairs of nodes. Set of the whole edges is defined as E.

C is the channel allocation map that assigns channels to element of U. I is an indicator function of edge which takes two nodes as input parameters. This

(17)

Figure 3.1: Notation conventions

function checks whether edge between the two nodes exists or not.

3.2 Problem Formulation

For the proposed algorithm, we allocate channels in orthogonal channel set as mentioned in Section 1. The usage of 802.11 non-orthogonal channels induces ACI and ACI possibly can induce problem similar to hidden node problem[4].

So we only consider channel maps allocating channels in orthogonal channel set.

And we take assumption that all APs in this system have the information of the whole carrier sense relationships. It is possible because the proposed algorithm targets client assisted enterprise environment. To collect and share

(18)

the information the system might use backhaul, control message, reporting or other methods.

The goal of this algorithm is finding a channel assignment map C which min- imizes starvation occurrence. To reach the minimum exhaustive search should be done. But exhaustive search has very high complexity here, so proposed algorithm use heuristic method to attain suboptimal result.

3.3 Proposed Algorithm

The proposed algorithm consists of three steps. Graph generation, generation of candidate channel allocation maps, calculation and comparison of objective function. The flowchart of this algorithm is exhibited in Figure 3.2. At first, generate the carrier sense relationship graph by using gathered carrier sense relationship information. Then, generate candidate channel allocation maps.

At the first time, it starts with random channel allocation map C. Then, pick an AP u_n and generate new channel allocation maps by altering channel of the AP. If there is any C^′ which has objective function value lower then that of C^′, then set the C^′ as new C. Same things will be done for every AP in the system sequentially. Order of picking AP is in descending order of degrees of those APs. Then, check whether there is any AP that changed its channel during processes. If exists, go back to the first AP picking procedure and do

(19)

Figure 3.2: Flowchart

same things again and again. Pseudocode is presented in Figure 3.3. The σ function used here refers to permutation function {1, . . . ,|U|} → {1, . . . ,|U|}.

This function satisfies that if σ(i)< σ(j), then

|U|

X

k=1i̸=k

I(u_i, u_k). The permutation functionσ helps us to consider the high-degree nodes preferentially.

The objective function consists of summation of three terms and is shown in Figure 3.4.α(uk) is representing the occurrence of hidden node problem and β(u_k) is representing the occurrence of carrier sense starvation and γ(u_k) is representing the severity of contention. The variables w₁, w₂, w₃ are weighting factors. These values should be determined properly depending on the environment.

(20)

Figure 3.3: Pseudocode of proposed algorithm

Figure 3.4: Objective function of proposed algorithm

(21)

Chapter 4

Simulation Results

In this chapter, results of simulation are presented. Results of LCCS and Hmin- max in same environment is also presented for comparison. Following contents contain illustrative simulation results in 3 different situations. Simulations are done by NS-3 (Network Simulator 3) and the environment for simulations are briefly described in Figure 4.1. And topologies used in simulation are presented in Figure 4.2.

Figure 4.1: Simulation environments

(22)

Figure 4.2: Topology of situation 1

(23)

(24)

(25)

Simulation 1, 2, 3 are performance comparison of LCCS, Hminmax and proposed algorithm. Proposed algorithm is conducted with 4 different weights {w₁, w2, w3, w4}. In situation 1 and 2, carrier sense relationship is fragile to hidden node starvation occurrence and carrier sense starvation each. In situation 3, STAs are randomly distributed in cell of its associated AP. Simulation topologies and goodput bar graphs are presented in Figure 4.3 and sum throughput and Jain’s index of simulation results are recorded in Table 4.1.

(26)

(27)

(28)

(29)

Regular LCCS Hminmax Proposed Avg goodput 3.35Mbps 2.42Mbps 3.14Mbps 2.42Mbps

Jain’s index 0.735 0.597 0.703 0.597

(a) Performance comparison of situation 1

Jain’s index 0.830 0.552 0.520 0.609

(b) Performance comparison of situation 2

Jain’s index 0.758 0.484 0.578 0.591

(c) Performance comparison of situation 3

Table 4.1: Throughput and fairness comparison

(30)

Chapter 5

Conclusion

In this paper, we have proposed novel anti-starvation channel allocation algorithm. With assistance of associated STAs and the information of carrier sense relationship, it is able to predict possible occurrence of starvation problems. By utilizing this information, this algorithm reduces the occurrence of starvation problems. In this way, the proposed algorithm enhances fairness of dense 802.11 enterprise system.

(31)

Bibliography

[1] M. Achanta, ”Method and apparatus for least congested channel scan for wireless access points,” U.S. Patent No. 20060072602, April 6, 2006.

[2] A. Mishra, V. Brik, S. Banerjee, A. Srinivasan and W. Arbaugh, “A client- driven approach for channel management in wireless LANs,” in Proceed- ings of IEEE International Conference on Computer Communications, Barcelona, Spain, Apr. 2006. pp. 1-12.

[3] C. Hua, “Starvation modeling and identification in dense 802.11 wireless community network,” inProceedings of IEEE International Conference on Computer Communications, Anchorage, Alaska, USA, May 2007. pp. 1022- 1030.

[4] J. Nachtigall, A. Zubow and J. Redlich, “The impact of adjacent channel interference in multi-radio systems using IEEE 802.11,” inProceedings of

(32)

IEEE International Conference on Wireless Communications and Mobile Computing, Crete Island, Greece, Aug. 2008. pp. 874-881.

[5] A. Mishra, S. Banerjee and W. Arbaugh, “Weighted coloring based channel assignment for WLANs,” Newsletter ACM Mobile Computing and Com- munications Review, vol. 9, no.3, pp.19-31, July 2005.

(33)

초록

최근802.11장치의 밀도가 빠른증가세를 보이면서802.11 네트워크에서 기아

현상이심각한문제가되고 있다. 802.11네트워크에 대한기존의몇가지채널 할당 알고리즘이 있지만 기존의 알고리즘들은 기아 문제 처리에 어려움을 가

지고있다.고밀도환경에서 사용자 경험을 개선하기위해서는이 기아문제의 해결이필수적이다.따라서본고에서우리는효율적으로기아문제를완화시킬 수 있는 새로운 채널 할당알고리즘을제안한다. LCCS및Hminmax는전송율 합 극대화에 주목적을 두고 있는데 반해 이 새로운 알고리즘은 기아를 겪는

노드를 구제하는 데 목표를 둔다. 이 새로운 알고리즘은 carrier sense기아와

hidden node기아의두 가지유형의기아발생을감소시키고,시스템공정성을

향상시킨다.

주요어:무선랜, 802.11, 채널 할당,기아방지,공정성 향상 학번: 2010-23242

(34)

Acknowledgements

드디어 졸업을 앞두고 있습니다. 좀 더 차분하게 고민하면서 잘 다듬어진 ac-

knowledgements를 쓰고 싶었는데 새로운 곳으로 간다는 설렌 마음에 그렇게

하지는 못할 것 같습니다. 대신 아무런 고민없이 진심을 담은 감사의 말씀을 써내려갈 수 있을것 같습니다.

우선은 교수님께 감사의 말씀을 드리고 싶습니다. 철없고 못난 저를 3년 동안 거두어 보살펴주시고 마지막 저의 진로에도 많은 관심 기울여 주셔서감사합 니다. 처음 연구실 들어왔을 때의 저를 생각하면 천둥벌거숭이처럼 날뛰었던 것 같은데 이제는 차분하게 저의 자리를알고 다른 사람을 배려할 줄 알게 된

것 같습니다. 항상 모난 모습으로 살다가 드디어 자갈이 되어 여러 사람과 함 께 부대끼며 사는 법을 교수님께 배운 것 같아 사회로 나가는 길이 두렵지가 않습니다.

그리고 연구실의 선후배들께도 고맙다는 말을 꼭 하고 싶습니다. 제일 막내 였던 저에게도언제나 친근하게 말 걸어주신 길남이형,연구실 인턴하는 동안 늘 즐겁게해주신 병옥이형,무선랜팀 일하면서 가장 많은 것을가르쳐주시고

(35)

팀원들을 잘 이끌어주신형주형,좀무섭지만 후배들 은근히 챙기시는동현이 형,신입생때 저희를 잘 인솔해주셨던 건일이형,연구실의 선후배를 이어주는 품격있는 보수 두희형, 어리고 모자란 선배인 저한테도 너무나 잘해준 준호

형,같은버스타고내려가면서여러가지 조언해주신태욱이형,제가제일 닮고 싶어하는 부드러운 카리스마 선익이형,어리바리하고 일 잘 못했던 석사들 잘 챙겨주신 재성이형, 여러가지 고민 잘 들어주셨던 한영이형, 터프한 레이서

상우형, 똑똑하고 아이디어가 많은 준수형, 허당이지만 나름대로 의리있는 원 준이형, 매사에 열심히 하는 모습이 멋진 경수형,귀엽다고 하면 좀 그렇지만 아무튼 뭐 그 저 재밌고 착한 준영이, 내년엔 서로 다른 곳에 있지만 여전히 같은 야구를 볼 진엽이,함께한 시간은 짧지만 그래도 생각이 많이 날 승민이 와 우현이까지.모두모두 감사합니다.앞으로 어디서 어떻게 만나더라도 많이 제가도울 일이 있었으면 좋겠습니다.

그리고 앞으로 계속 공부 오래 할 중린이, 박사까지 무사평탄하게 잘 해내길

바란다.승엽이현삼이수왕이연호 항녕이 수린이 준행이 테라형 슬기형서욱 이형병준이형등등 다들 잘 지내시길바랍니다.저는 한동안 멀리 갑니다. 마지막으로,공부욕심내느라학교 오래다니는아들 뒷바라지잘 해주신아버 지,어머니께 감사하다는말씀드리고싶습니다.바쁘단핑계로자주못내려갔

었는데진짜바빴습니다믿어주세요.많이늦었지만올해부터는자주내려가고 효도하겠습니다.그리고누나는하는일끝까지잘해서꼭변호사되고,세란이 는올해고3이라힘들겠지만올해잘해놓으면앞으로쭉좋은 일이많을거라는

(36)

생각가지고 끝까지 열심히 하기 바란다. 모두들¡Hasta la vista!