An energy efficient clustering scheme by adjusting group size in zigbee environment

(1)

Zigbee 환경에서 그룹 크기 조정에 의한 에너지 효율적인 클러스터링 기법

박종일

^†

·이경화·신용태

An energy efficient clustering scheme by adjusting group size in zigbee environment

Jong-il Park

^†

, Kyoung-hwa Lee, and Yong-tae Shin

Abstract

The wireless sensor networks have been extensively researched. One of the issues in wireless sensor networks is a developing energy-efficient clustering protocol. Clustering algorithm provides an effective way to extend the lifetime of a wireless sensor networks. In this paper, we proposed an energy efficient clustering scheme by adjusting group size. In sensor network, the power consumption in data transmission between sensor nodes is strongly influenced by the distance of two nodes. And cluster size, that is the number of cluster member nodes, is also effected on energy consumption.

Therefore we proposed the clustering scheme for high energy efficiency of entire sensor network by controlling cluster size according to the distance between cluster header and sink.

Key Words :clustering, wireless sensor network, zigbee, power saving scheme, LEACH

1. 서 론

Zigbee ^{환경에서는}^에너지를^{효율적으로}^활용하기

위해계층적라우팅방법인클러스터링을활용한다. 각 센서노드들은클러스터에게자신의센싱데이터를전

송하고헤더는이를수집하여 Sink 노드에게전달함으

로써모든노드가 Sink로데이터를전송하는부담을

줄여전체네트워크의에너지효율을극대화한다.

최근클러스터링을활용한전송프로토콜이많이연 구되었으며^[1,2], 그중대표적인프로토콜로는 LEACH (low energy adaptive clustering hierarchy)^와 HEED(hHy- brid, energy-efficient approach) 등이있다. LEACH는 확률적인방법에의해일정시간동안헤더를변경하

는방식이며, HEED^는^각^노드의^잔여^{에너지양에}^따

라 클러스터 헤더를 선출하는 방식이다. 그러나

LEACH나 HEED의경우각클러스터의에너지소비

에대한형평성을고려하지않고있기때문에, ^전체^에

너지효율이떨어진다는단점이나타날수있다.

본논문에서는소규모 Zigbee 환경에서위와같은

단점을극복하고에너지효율성을높이기위해 Sink^와

거리에따라클러스터의크기를조절하여에너지효율 을높일수있는클러스터링기법을제안하고자한다.

본논문의 2장에서는관련연구로써기존에제안된 클러스터링기법을살펴본다. 3장에서는제안하는클 러스터링알고리즘을제시하고, 4^장에서는^제안하는

알고리즘의성능평가를수행한다. 5장에서는끝으로 결론및향후연구방향을제시한다.

2. 관련 연구

LEACH^는^{클러스터링}^기반^라우팅^기법으로, ^클러

스터헤드가클러스터의멤버노드들로부터데이터를 수집하여직접싱크로전달한다. 이기법의특징은네 트워크에있는모든센서노드들에에너지소비를공 정하게분산시키기위해, 에너지집약적인기능을하는 클러스터헤드를무작위로순환시키고, 전체적인통신 비용을줄이기위해클러스터헤드에서클러스터내의 데이터를모아지역적으로 aggregation하는것이다.

*숭실대학교대학원컴퓨터학과(Dept. of Computer Science, Graduate School of Soongsil University)

†Corresponding author : [email protected]

(Received : May 25, 2010, Revised : August 2, August 26, 2010 Accepted : August 26, 2010)

(2)

각라운드는크게클러스터가형성되는 Setup 단계

와 여러개의 TDMA ^{프레임으로}^구성되는 Steady-

state 단계로구성된다. Setup 단계의시작에서모든노

드는자신이현라운드동안클러스터헤드가될수있 을지에대해이전라운드들동안클러스터헤드였는지 의여부와이상적클러스터헤드수에기반을두고결 정한다.

현라운드동안, 클러스터헤드로결정된경우, 이를 이웃센서노드들에알린다. 이를수신한비클러스터 헤드노드들은수신강도등의파라미터를기반으로클 러스터헤드를결정하며, 이를클러스터헤드로전송하 여클러스터가구성된다. 클러스터가형성되면, 클러스 터헤드는클러스터멤버들의데이터전송순서를지시 하는 TDMA 스케줄을방송하고, Steady-state 단계로

간다. Steady-state 단계에서각클러스터멤버노드들

은자신의전송슬롯에서만데이터를전송하고나머지 슬롯들에서는 sleep 모드로가서전력소모를줄인다.

LEACH에서는클러스터내부에서는 TDMA를사용

하여노드간간섭을피하고, ^{클러스터간의}^간섭을^피하

기위하여각클러스터들이서로다른확산코드를사 용하는방법을채택한다.

LEACH의성능은매라운드마다일정한수의클러

스터를구성하고, 클러스터헤드가고르게배치되는데 있으나, ^자기^스스로^선출하는^{방법으로는}^이를^보장할

수가없다. 또한각클러스터마다지정된노드의수를 결정할수있는제한이나규칙이없기때문에, 각클러 스터별에너지소비률에차이가발생한다. ^싱크에서

센서노드의위치정보와에너지보유량을고려하여,

클러스터 헤드와 클러스터를 결정하는 LEACH- C(LEACH-centralized) ^기법도^{제안되었다}.

LEACH-C는클러스터헤더의결정권을 Sink에게넘

김으로써헤더결정에따른에너지소모를줄인다^[4].

Sink^는^헤더^결정을^위해^각^노드들의^위치와^에너지^정

보를확인하여클러스터헤더를결정하는기법이다. 그

러나 LEACH-C는위치와에너지정보확인을위한부

가적인오버헤드가발생하고라운드마다 BS와통신을

하기위한에너지손실률이매우크다. 그러나 LEACH-

C ^역시^{클러스터의}^규모에^대한^별다른^정의가^없으므

로모든클러스터의균등한에너지소비를보장할수 없기때문에, 전체적인에너지효율은낮아지게된다.

본논문에서는클러스터와 Sink ^간의^전송은^중계

없는직접통신으로가정하여처리한다. 이것은중계할 경우한클러스터영역의데이터를중계해야할노드 의에너지소모량이클러스터헤더와비슷해지므로전 체적인센서네트워크의에너지소모량이증가하게되

기때문이다. 게다가헤더와헤더간의통신에의해전 송을하게될경우, ^중계^역할을^수행하는^헤더의^에너

지소모량은중계에참여하지않는클러스터헤더의 약 2배이상의에너지를소모하게된다. 따라서모든

노드가 Sink와직접통신이가능한영역에서의센서

네트워크인경우, 클러스터와 Sink 간의전송은중계 없는직접통신방식이적합하다.

이와같은상황에서의클러스터링은 Sink와의거리 에따라서클러스터헤더가소모하는에너지양이달라 진다. ^센서^{네트워크에서의}^에너지^소모량은^전송^거리

의제곱에비례하기때문에 Sink와인접한클러스터

헤더는원거리의클러스터헤더보다에너지소모율이

적다. ^즉 Sink^와의^거리가^멀면^멀수록^센서의^생존^시

간이짧아지게되고이는곧전체센서네트워크의수 명을단축시키게된다. 따라서모든클러스터의균등한 에너지소비량을유도함으로서전체네트워크의수명 을증가시킬수있게된다. 본논문에서는클러스터의 노드수를조절하여각클러스터에서에너지양을균등 하게소모하여전체네트워크의수명을늘릴수있는 클러스터링기법을제안한다.

3. 그룹크기 조절에 따른 클러스터링

3.1. 제안하는 클러스터링 기법

본논문에서제안하는클러스터링알고리즘은 Sink

와의거리에따라클러스터들의에너지소모량이일정 하도록각클러스터의크기를조절하는것으로, ^이때

클러스터의크기는멤버노드의개수가된다. 센싱영

역의모든노드는자신의위치정보를바탕으로 Sink

와의거리를계산한다. ^이때^계산된^거리^값은^노드들

을 Class화하는데사용한다. 즉, 모든노드들을 Sink와

의거리값에따라 Sink에인접한노드들부터 Class 0

부터 Class n^으로^구분하고, ^이 Class^에^따라서^그룹의

크기를지정하는것이다. 제안하는클러스터링알고리 즘의전체적인알고리즘은다음과같다.

① Sink는자신의위치정보와기준값을센싱영역 전체에방송

② 각노드는 Sink^의^{위치정보와}^자신의^{위치정보로}

거리를계산

③ 각노드는기준값과계산된거리값으로자신의

Class^를^결정

④ 각 Class 중간지점의일부노드는클러스터헤드

공지

⑤ 클러스터설정후일정라운드까지데이터전송

⑥ 일정라운드이후클러스터헤더이주

(3)

노드의 Class 구분을위한기준값은 W. B. Heinzel- man^이^제안한^센서^{네트워크의}^에너지^소비^모델^[7]^에

서근거리와원거리전송을구분하는거리값인를활 용하여도출한다.

Class^에^따른^{클러스터의}^크기는 Class 0 > Class 1

> ... > Class n이되도록지정한다. 본논문에서는클 러스터링알고리즘을그범위로하기때문에, 클러스터 헤더의재선출및이주와관련된사항은향후연구에서 다루도록하겠다. 제안하는클러스터링기법을도식화 하면 Fig. 1과같다.

3.2. 클러스터 에너지 소모량 분석

W. B. Heinzelman^은^한^센서^노드에서^소모되는^에

너지양을분석하기위해다음의식을사용하였다^[6,8]. (3)

여기서l은데이터크기, Eelec은송신에서의소모되 는전자에너지(electronics energy)^이고, ^는^짧은^거

리송신을위한증폭에너지(amplifier energy-free space

model), d는수신자와송신자사이의전송거리, 는

먼거리송신에필요한증폭에너지(amplifier energy-

multipath model)이다. 이때 라고하면, 는다

음과같다^[6,7].

(4)

l bit ^메시지를^{전송받는데}^드는^{에너지양은}^다음과

같다.

(5)

Sink가전체센싱영역의중심에있으며, 클러스터

헤더와 Sink 간거리ds가 라고가정할때, 클러

스터헤더가한라운드에서소모하는에너지양은다음 과같이구할수있다.

(6)

전체센싱영역이 이라고할때, n은센서노 드의개수, nc는클러스터헤더의개수를나타내며, EDA는데이터 Aggregation에소모되는에너지이며, lA

는 Aggregation^된^데이터^크기를^나타낸다. l^과lA는다 음과같다.

(7) (8)

여기서 는 패킷의 header, 는 데이터, 는

footer의길이를각각나타낸다. 헤더와의거리가 인

일반노드에서의에너지소모량은다음과같다. (9)

따라서한클러스터에서소모하는전체에너지양은 다음과같다.

(10)

3.3. 균등한 에너지 소모를 위한 클러스터 간 노드 개수 두클러스터 A와 B가존재하며클러스터 A가클러

스터 B^에^비하여 Sink^에^인접해^있다고^가정할^때, ^각

클러스터헤더의에너지소모량은식 (6)를통해서얻 을수있다. 각클러스터의멤버노드의수가N으로동 일하고클러스터 A의헤더와 Sink 간의거리가d1, 클 러스터 B의헤더와 Sink 간의거리가 d2일때, 이두 값은식 (6)에적용하면, A 헤더의에너지소모량은

(11)

이며, B ^헤더의^에너지^소모량은

(12)

가될것이다. 여기서 이므로, 가된다. d1과d2를변경할수없는상황에서두클러스터헤 더의에너지소모량이같아지도록하기위해서변경할

수있는값은N뿐이다. 즉 Sink와가까운클러스터 A

의멤버노드수를증가시키거나, 먼클러스터 B의멤

ET( )l d, lEelec+lεfsd² ifd d≤ ⁰

lEelec+lεmpd⁴ ifd d> 0

⎩ ⎭

⎨ ⎬

⎧ ⎫

=

εfs

εmp

d d= 0 d0

d0= εfs⁄εmp

ER( )l =lEelec

ds≤d0

ECH^{( )}l n nc

---- 1–

⎝ ⎠

⎛ ⎞lEelec n nc

----lEDA lAEelec lAεfsdS²

+ + +

=

M M×

l l= H+ +lD lF

lA lH n nc

----lD lF

+ +

=

lH lD lF

dH

EnonCH( )l =lEelec+lεfsdH²

Ecluster ECH n nc

----EnonCH

+

≈

EA=(N–1)lEelec+NlEDA+lAEelec+lAεfsd12

EB=(N–1)lEelec+NlEDA+lAEelec+lAεfsd22

d1<d2 EA<EB

Fig. 1.Proposed clustering scheme.

(4)

버노드수를감소시킴으로서두클러스터헤더의에 너지소모량을동일하게만들수있다. ^이러한^방식으

로전클러스터의에너지소모량을균형있게만들어 센서네트워크의 Life time을증가시킬수있게된다.

전체적인 Life time을증가시키기위해서는에너지

소모가적은클러스터를기준으로삼는것이적당하기 때문에, 클러스터 B의멤버노드수를감소시킨다.

클러스터 B의멤버노드수를α만큼감소시킨다고 할때, α를식 (12)에적용한다.

(13)

여기서 일때, α를도출하면다음과같다. (14)

3.4. Class화를 위한 기준값 도출

Class화를위한기준값은에너지소모량에영향을주

는요소이지만, 큰비중을차지하지않는다. 이것은전 체센싱영역의넓이, 센서노드의초기에너지양, 최 적화된클러스터의개수, ^또는^실험에^따른^적정^값으

로도출할수있다.

본논문에서는각센서노드는자신의 Class를정하

기위해 Sink^와의^거리와^에너지^소비^모델의d0로도

출한기준값을사용한다. Sink로부터센싱하는전체영

역의가장먼가장자리까지의거리가R일때, 기준값

dt는다음과같다.

① if (No Classification)

② if (2 Classification)

③ if (3 Classification)

본논문에서는R^이 2d0보다클경우도③의값을기 준값으로한다. 추가적으로 Class에따른클러스터의 개수를최적화하면좀더효율적인에너지소모율을 갖는알고리즘을구현할수있다. W. B. Heinzelman^이

제안한최적화된클러스터의개수는다음식 (15)과같 다^[6].

(15)

여기서d^는 Sink^와의^거리를^나타내며, ^은^전체^노드

N의개수, M은센싱영역의한변을나타낸다^[6]. W.

B. Heinzelman은식 (15)을통해 영역에서노드

가N^개^일^때의^최적화된^클러스터^개수를^구할^수^있

다. 이를본논문에적용하여, 각 Class 별로최적화된 클러스터개수를구한다.

(16)

Class의최적화된클러스터개수 는 Class의노

드개수 와클래스면적 , Class에속한노

드와 Sink ^간의^평균^거리dC를사용하여구한다. ^여기

서도출된클러스터개수는한클러스터의멤버노드 수, 즉클러스터의크기를결정하는데사용할수있을 것이다.

4. 성능 평가

본논문에서제안하는기법의성능평가를위한환경 설정은다음과같다.

각클러스터에서 Sink^로^데이터를^전송하는^방법은 1-hop 또는 Multi-hop이될수있으나, 본논문에서설 정한환경하에서, 근거리전송과원거리전송에대한 증폭에너지의기준값인d0[3]가전체전송영역의반경

보다크기때문에, 클러스터헤더와 Sink 간의전송은

중계없는 1-hop 전송방식으로처리된다고가정한다.

따라서본논문에서는클러스터헤더와 Sink ^간의

전송은중계없이이루어진다고가정할때, 한클러스 터링영역의에너지소모량에큰영향을주는것은멤

버노드의수와 Sink까지의거리이다. 이러한환경하

에서노드의수와 Sink까지의거리에변화를주어측

정한결과는 Fig. 2^와^같다.

Fig. 2로알수있는것은멤버노드수의증가보다

Sink와의거리차에따라에너지소모량이크게증가

한다는것이다. ^위의^환경에서^거리에^따라^두^클러스

터의에너지소모량을동일하게하기위한α는 Fig. 3

EB=⁽N– 1^α– ⁾lEelec+⁽N–^α⁾lEDA+lAEelec+lAεfsds²

EA=EB

α εfs(d22–d12)lA

l E⁽ elec+EDA^{) ε}– fsd²² ---

=

R d^≤2---- ⁰^,^d^t=0 d0

2----^<^{R d}^≤ ⁰^,^d^t=^d2----⁰ d0<R≤2d0,dt 2d0

---3

=

kopt N 2π

--- ^ε^fs

εmp

---^M d² ---

=

Network grid Length of Data Length of Header

Length of Footer Electronics energy, Data Aggregation energy,

Transmitter energy, Amplifier energy,

M M×

kc opt– NClass

2π

--- ^ε^fs

εmp

---^M^Class dC²

---

=

kc opt–

NClass MClass

100m^×100m 1000bit

310bit 2bit Eelec 50nJ bit⁄

EDA 50nJ bit report^⁄ ^⁄

εfs 10nJ bit m⁄ ⁄ ² εmp 0.0013pJ bit m⁄ ⁄ ⁴

d0= εfs⁄εmp 87m

(5)

과같이나타난다.

Fig. 3은두개의클러스터에대해서, 각클러스터헤

더와 Sink의거리가 Fig. 3의 X축의값과같을때, 식

(13)^과 (14)^에^이때의^멤버^노드^수와^거리^값을^적용

한결과이다. 거리의차가늘어날수록α는기하급수적 으로 증가하게된다. α의값이 너무크게될 경우

Class^별^{클러스터의}^멤버수가^너무^큰^차이를^보이게

되므로적절한조절이요구된다.

위의환경설정과α를적용한본논문의성능평가 를위한시뮬레이션환경은 Fig. 4^와^같다.

통신중에나타나는저항값은일정하며통신거리에 따라서만잔여에너지양이달라진다. 초기에각센서노

드에설정된에너지가 2J이라고할때 LEACH^와^제안

하는기법의에너지소모량에따른노드생존율은 Fig.

5와같다.

Fig. 5의결과에서볼수있듯이모든노드의생존시

간이 LEACH ^보다^제안하는^기법이^오랫동안^지속되

는것을확인할수있다. LEACH의경우 146 round

이후부터네트워크에참여하는노드의수가감소하는

반면, ^제안하는^기법의^경우 189 round ^이후부터^참여

Fig. 2.Energy consumption of cluster header according to node number and distance.

Fig. 3.Differential value. Fig. 4.Simulation Environment.

Fig. 5.Simulation result.

(6)

노드의수가감소한다. 즉제안하는클러스터링기법의

전체네트워크생존율이 LEACH^보다 1.3^배^높다. ^비

록전체노드가자신의모든에너지를소모하는시점

은 LEACH가더길지만, 이때의노드생존율이 40 %

미만이되기때문에, 네트워크가유지된다고보기는어 렵다.

5. 결 론

멤버노드의데이터를수집하여 Sink^로^보내는^클러

스터링기법의경우대부분의에너지는데이터의전송

에사용되며, 이때소모되는에너지는 Sink와의거리와

멤버노드의수에큰영향을받게된다.

본논문에서는 Sink와의거리에따라클러스터의멤 버노드수를조절하여전체적인에너지효율을높일 수있는클러스터링기법을제안하였으며, ^제안한^알고

리즘을 LEACH와의비교분석을통해 30 % 이상높

은에너지효율을보임으로서성능의우수성을입증하 였다.

향후에는 Class화를위한최적의기준값도출및각

Class 별최적의클러스터개수도출등과관련된추가

적인연구를통해본논문을보완하여더욱에너지효 율성을높일수있는방안을연구하고성능평가를통 해우수성을입증하도록하겠다.

감사의 글

본연구를위해힘써주신신용태교수님과함께연 구를진행한이경화박사과정등선후배님들께감사의 말씀을드립니다.

참고 문헌

[1] D. Estrin, L. Girod, G. Pottie, and M. Srivastava,

“Instrumenting the world with wireless sensor networks”, Acoustics, Speech, and Signal Processing, vol. 4, pp. 2033-2036, 2001.

[2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102- 114, 2002.

[3] W. Heinzelman, A. Chandrakasan, and H. Bal- akrishnan, “Energy-efficient communication protocol for wireless microsensor networks”, System Sciences, vol. 2, pp. 10-19, 2000.

[4] W. Heinzelman, A. Chandrakasan, and H.Balakrish- nan. “An application-specific protocol architecture for wireless microsensor networks”, IEEE Transac- tions on Wireless Communication, vol. 1, no. 4, 2002.

[5] O. Younis and S. Fahmy, “HEED: A hybrid, energy- efficient, distributed clustering approach for Ad Hoc sensor networks”, IEEE Transactions on Mobile Computing, vol. 3, no. 4, pp. 366-379, 2004.

[6] W. B. Heinzelman, “Application-specific protocol architectures for wireless networks”, IEEE Trans- actions on Wireless Communications, vol. 1, no. 4, 2002.

[7] X. Wu, M. A. U. Khan, J. Cho, S. Y. Lee, and Y.- K. Lee, “Energy-efficient clustering with fast data compression in sensor networks”, International Conference on Hybrid Information Technology (ICHIT'06), Cheju Island, Korea, Nov 9-11, 2006, ISBN 0-7695-2674-8, IEEE Computer Society, pp.

403-408.

[8] S. Bandyopadhyay and E. J. Coyle, “An energy efficient hierarchical clustering algorithm for wireless sensor networks”, Proceeding of INFOCOM, 2003.

[9] Singh. V. Kumar, H.-T. Lim, and W.-Y. Chung, “A wireless sensor network approach to enable location awareness in ubiquitous healthcare applications”, J.

Kor. Sensors Soc., vol. 16, no. 4, pp. 277-285, 2007.

1

월

Michigan state University