Advanced
Tradeoff Analysis of Consensus Algorithm in Distributed Wireless Networks
Tradeoff Analysis of Consensus Algorithm in Distributed Wireless Networks
Journal of the Korea Institute of Information and Communication Engineering. 2014. May, 18(5): 1080-1086
Copyright © 2014, The Korea Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : April 01, 2014
  • Accepted : April 29, 2014
  • Published : May 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
현호 최
hhchoi@hknu.ac.kr

Abstract
본 논문에서는 CSMA/CA기반의 분산 무선 네트워크에 컨센서스 알고리즘을 적용할 때 발생하는 트레이드오프 성능을 분석한다. 컨센서스 알고리즘 자체는 협력 이웃 노드가 많을수록 빠른 수렴 속도를 갖지만, 무선 네트워크상에서는 협력 이웃 노드가 많을수록 접속 충돌로 인하여 전송 지연이 증가한다. 따라서 두 성능 간에 트레이드오프가 존재하며, 이로 인하여 컨센서스 달성 시간을 최소화하는 최적의 협력 이웃 노드 수가 존재한다. 시뮬레이션을 통하여 컨센서스 참여 노드 수에 따라 최적 이웃 노드 수를 도출한 결과, 네트워크 규모가 작을 때에는 모든 노드가 다 같이 협력하는 것이 최적이지만 네트워크 규모가 어느 이상으로 커질 경우에는 이웃 노드 수를 일정 값으로 제한하는 것이 최적 운용 전략이 된다.
Keywords
Ⅰ. 서 론
컨센서스(consensus)란 각 노드의 상태에 의존하는 어떠한 값이 서로 일치하게 됨을 의미하며, 컨센서스 알고리즘은 컨센서스를 위해 각 노드가 네트워크상의 이웃 노드들과 관련 정보를 공유하는 상호 규칙을 일컫는다 [1] . 컨센서스 알고리즘은 분산 시간 및 주파수 동기화 [2 , 3] , 분산 공평(round-robin) 자원 할당 [4] , 빠른 분산 데이터 공유 [5] , 센싱 정보의 분산 퓨전 [6] 등 컨센서스가 필요한 다양한 통신 네트워크 응용 분야에 접목되어 사용되어 왔다.
이때 관심을 갖는 성능 지표는 얼마나 빨리 컨센서스를 달성할 수 있느냐에 관한 것으로, 이는 컨센서스 알고리즘의 제어 파라미터와 네트워크 환경에 영향을 받는다 [7] . 하지만 지금까지의 컨센서스 관련 연구는 알고리즘 자체의 수렴 여부와 수렴 속도에 중점을 두었지 실제 네트워크 환경에서 노드 간 상태 정보 교환에 의해 발생하는 전송 지연에 대해서는 고려하지 않았다 [1 , 8 , 9] . 컨센서스 알고리즘 자체의 수렴 속도는 일반적으로 노드 간 정보 공유가 많을수록, 즉 노드 당 이웃 노드수가 많을수록 빨라진다. 따라서 컨센서스를 이루고하 하는 네트워크상의 모든 노드들이 다 같이 협력하는 것이 컨센서스를 달성하는데 걸리는 시간을 최소화하는 이상적인 방법이 된다 [8 , 9] . 하지만 컨센서스 알고리즘이 수행되는 실제 네트워크 환경을 고려하면 상호 정보교환을 수행하는 이웃 노드 수가 증가할수록 전송 지연이 증가하고 협력 오버헤드가 커지므로 전체적인 컨센서스 알고리즘의 성능에 이들 요소를 고려해야 한다. 특히 컨센서스 알고리즘은 주로 분산 네트워크 환경에서 중앙의 제어 없이 노드 간 정보 공유가 이루어지므로 이웃 노드 수의 증가는 전송 패킷의 충돌로 인하여 전송 지연의 급격한 증가를 야기한다 [10] . 따라서 실제 무선 네트워크 환경에서 컨센서스 알고리즘은 정보를 공유하는 이웃 노드 수에 따라 트레이드오프(tradeoff) 성능이 존재함을 알 수 있다. 즉, 협력하는 이웃 노드 수가 증가함에 따라 알고리즘의 수렴 속도는 빨라지지만 노드 간 정보 교환에 따른 전송 지연의 증가로 인하여 알고리즘 동작 시간이 증가한다.
본 논문에서는 가장 일반적인 CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance) 프로토콜을 사용하는 분산 무선 네트워크 환경에서 주어진 노드들이 컨센서스를 달성하고자 할 때, 노드 당 협력 이웃 노드 수에 따른 컨센서스의 성능 변화를 살펴본다. 이를 기반으로 전체 참여 노드 수에 따라 컨센서스 달성 시간을 최소화하기 위한 최적 파라미터를 도출하고, 분산 무선 네트워크 환경에서 최적 컨센서스 프로토콜의 운용 방법을 제시한다.
본 논문의 구성은 다음과 같다. Ⅱ장에서는 본 논문에서 고려하는 컨센서스 알고리즘을 소개하고 수렴 특성을 설명한다. Ⅲ장에서는 CSMA/CA 프로토콜을 사용하는 분산 무선 네트워크에서 패킷 전송 지연을 수학적으로 도출하고 컨센서스 달성 시간으로의 영향을 분석한다. Ⅳ장에서는 시뮬레이션 결과를 도출하고 트레이드오프 성능 및 최적화 방안에 대해서 고찰한다. 마지막으로 Ⅴ장에서 본 논문에 대한 결론을 맺는다.
Ⅱ. 컨센서스 알고리즘
컨센서스 알고리즘은 연속/이산시간에 따라, 수신한 주변 이웃 노드들의 상태 값의 처리 방식에 따라 몇 가지 변형된 형태가 존재하는데, 본 논문에서는 다음 식으로 표현되는 이산시간 기반의 컨센서스 알고리즘을 고려한다 [1] .
PPT Slide
Lager Image
여기에서 xi ( k )는 k 시간에 노드 i 의 상태 값, Ni 는 노드 i 와 통신 가능한 이웃 노드의 집합을 나타내고, | Ni |는 노드 i 의 이웃 노드의 개수를 나타낸다. 이 컨센서스 알고리즘에 따르면 각 노드는 현재 자신과 이웃 노드들의 상태 값의 평균으로 다음 상태 값을 결정한다. 즉, 각 노드는 주변 이웃 노드들의 상태 정보만을 가지고 분산적으로 지역적인 평균(local average)을 취한다. 이와 같은 반복 동작은 수행 횟수가 증가함에 따라 모든 노드의 상태 값이 동일한 값으로 수렴하게 되는(즉, xi xj i,j ) 컨센서스를 이루게 된다.
또한 식(1)은 다음과 같은 행렬 연산 형태로 표현 가능하다 [1] .
PPT Slide
Lager Image
전체 참여 노드 수가 N 이라고 할 때 I N N 단위 행렬이며, D 는 주대각 성분이 각 노드의 이웃 노드 개수인 대각 행렬이며, A i , j 노드 간 연결성을 나타내는 인접 행렬(adjacency matrix)이다. 이때 페론(Perron)이라 불리는 행렬 P 는 ( I + D ) -1 ( I + A )로 정의되는데, 이론적으로 행렬 P 의 두 번째로 큰 고유값이 작을수록 컨센서스 알고리즘의 수렴이 빠르다는 사실이 밝혀져 있다 [1 , 8] .
이와 같이 지금까지 연구된 컨센서스 이론은 컨센서스 알고리즘의 수렴여부 및 수렴속도의 경향성은 알려주지만, 실제 컨센서스가 달성되기까지 걸리는 시간은 계산해주지 못한다. 따라서 본 논문에서는 식(1)의 컨센서스 알고리즘의 수렴 여부와 수렴 속도에 대한 이론적 결과를 바탕으로 노드 간 연결 토폴로지와 노드별 상태값 분포 등의 다양한 환경 변수를 반영한 시뮬레이션을 통하여 컨센서스 달성 시간을 구한다.
Ⅲ. 분산 무선 네트워크에서의 컨센서스 알고리즘의 성능 분석
컨센서스 알고리즘은 노드 간 상태 정보의 교환을 필요로 하므로 이를 네트워크상에서 수행할 때 노드 간 패킷 전송 지연이 발생하게 된다. 고려하는 분산 무선네트워크에서는 CSMA/CA의 사용을 가정하여 컨센서스 알고리즘 동작시 발생할 수 있는 패킷 전송 지연을 도출하고 컨센서스 달성 시간에 반영한다. 본 논문에서는 경쟁 노드 수에 따라 접속 확률을 쉽게 제어할 수 있는 p -persistent CSMA 방식을 고려한다 [11] .
CSMA/CA 프로토콜에서 하나의 채널을 통해 모든 노드가 p 의 확률로 패킷을 전송하고자 할 때 발생하는 평균 전송 지연을 구하고자 한다. 먼저 노드 i 의 이웃 노드 수를 Ni 라 하고 이들 이웃 노드들이 노드 i 로 상태 정보가 담긴 패킷을 p -persistent CSMA 방식으로 전송한다고 할 때, 현재 타임 슬롯에서 한 명이라도 접속을 시도할 확률 Ptr 은 다음과 같다.
PPT Slide
Lager Image
또한 패킷의 전송 성공확률 Ps 와 전송이 없는 채널 휴지 시간 Tidle 은 각각 아래와 같이 계산된다.
PPT Slide
Lager Image
PPT Slide
Lager Image
여기에서 Ts 는 단위 타임 슬롯의 길이를 나타낸다. 패킷이 성공적으로 전달 될 때까지 재전송을 수행한다고 가정하면 Ni 의 노드가 경쟁할 때 발생하는 평균 패킷 지연은 다음과 같은 계산된다.
PPT Slide
Lager Image
여기에서 Tdata 는 전송하는 패킷 데이터의 시간 길이를 나타낸다.
컨센서스 알고리즘의 동작을 위해서는 네트워크상의 모든 노드들이 각자 자신의 주변 노드들과 상태 정보를 교환해야 한다. 이때 각 노드들은 자신의 정보를 주변 이웃 노드에게 매번 유니캐스트로 전송하는 것이 아니라 그림 1 과 같이 지역적인 브로드캐스트를 수행하게 된다. 따라서 한 노드의 한 번의 전송 성공은 브로드캐스트 전송의 성공을 의미하고, 이에 따라 주변 이웃 노드들은 이 노드에 대한 정보를 성공적으로 수신하게 된다. 이와 같은 맥락에서 각 노드가 주변 이웃 노드들과의 경쟁에서 성공하게 될 때까지의 시간 지연은 한번의 성공적인 채널 접속에 소요되는 시간이 되며, 경쟁하는 이웃 노드들 모두가 이를 이뤄야하므로 서로 정보를 교환하는데 걸리는 시간은 이웃 노드 수에 비례하여 선형적으로 증가하게 된다. 전체 네트워크상에서 모든 노드들이 동시 다발적으로 이러한 방식으로 패킷을 교환한다고 보면 평균 이웃노드 수가 Ni 이고 평균 패킷 지연이 D 일 때, 모든 노드들이 서로 패킷을 교환하는데 걸리는 시간은 점근적으로(asymptotically) NiD 가 된다.
PPT Slide
Lager Image
분산 무선 네트워크에서 컨센서스 알고리즘을 위한 지역적인 브로드캐스트의 개념 Fig. 1 A concept of local broadcast for consensus algorithm in the distributed wireless network
따라서 최종적으로 컨센서스 달성에 걸리는 시간( Tconsensus )은 시뮬레이션을 통해 구한 수렴에 필요한 알고리즘의 반복 횟수( Nitr )와 패킷 교환 지연 값( NiD )의 곱으로 다음과 같이 결정된다.
PPT Slide
Lager Image
Ⅳ. 시뮬레이션 결과 및 고찰
표 1 은 사용한 시뮬레이션 파라미터를 보여준다. 전송 관련 파라미터는 IEEE 802.11 표준의 OFDM 모드의 값을 참고하였고 [12] , 네트워크 토폴로지는 간단한 정규(regular) 네트워크 [1] 를 가정하여 각 노드별 이웃 노드 수를 동일하게 증가시켜가며 성능을 보았다. 초기에 각 노드의 상태 값은 0~100 사이에서 균일하게 결정되며, 컨센서스 알고리즘의 수렴조건은 모든 노드의 현재 상태 값과 이론적인 수렴 값의 차이 벡터의 2-norm 값이 10 -2 보다 작은 경우로 결정하였다 [13] . 시뮬레이션은 MATLAB을 사용하여 수행하였다.
시뮬레이션 파라미터Table. 1Simulation Parameters
PPT Slide
Lager Image
시뮬레이션 파라미터 Table. 1 Simulation Parameters
그림 2 는 참여 노드 수 N =100이고 각 노드의 평균 이웃 노드 수( Ni )를 각각 6명과 20명으로 설정하였을 때 알고리즘의 반복 횟수에 따른 각 노드의 상태 값의 변화를 보여준다. 컨센서스 알고리즘이 반복됨에 따라 처음에 다르게 분포되어있던 노드의 상태 값은 하나의 값으로 수렴하게 된다. 즉 컨센서스를 이루게 된다. 이때 상태 정보를 교환하는 협력 이웃 노드 수를 증가시킬 경우 수렴 속도가 매우 빨라짐을 확인 할 수 있다.
PPT Slide
Lager Image
알고리즘의 반복 횟수에 따른 각 노드의 상태 값의 변화 (a) 이웃 노드 수 Ni=6, (b) 이웃 노드 수 Ni=20 (참여 노드 수 N=100 일 때) Fig. 2 Evolution of state value of each node (Xi) versus number of iterations: (a) number of neighbors Ni=6 and (b) number of neighbors Ni=20 (when number of participating nodes N=100)
그림 3 은 참여 노드 수가 100이고 접속 제어 확률 값이 0.05일 때 협력 이웃 노드 수의 증가에 따른 컨센서스 알고리즘의 반복 횟수, 평균 정보 교환 지연, 컨센서스 달성 시간을 순서대로 보여준다. 이웃 노드 수가 증가할수록 알고리즘의 반복 횟수는 기하급수적으로 줄어들지만 노드 간 정보 교환 지연은 기하급수적으로 증가한다. 즉, 컨센서스 수렴 속도와 네트워크에서 발생하는 정보 교환 지연 간에는 트레이드오프가 존재한다. 따라서 이 두 성능의 곱으로 결정되는 컨센서스 달성 시간을 보면 아래로 볼록한 형태가 되며, 이 경우 이웃 노드 수가 36일 때 가장 빠르게 컨센서스를 달성함을 알 수 있다. 즉, 주어진 환경 변수에 따라 최적의 협력 이웃 노드 수를 찾음으로써 컨센서스 달성 시간을 최소화할 수 있다.
PPT Slide
Lager Image
협력 이웃 노드 수에 따른 (a) 수렴을 위한 컨센서스 알고리즘의 반복 횟수, (b) 평균 정보 교환 지연, (c) 컨센서스 달성 시간 (N=100, p=0.05일 때) Fig. 3 (a) number of iterations for convergence, (b) average information sharing delay, and (c) consensus time versus number of neighbors (when N=100, p=0.05)
그림 4 는 컨센서스에 참여하는 전체 노드 수에 따른 최적 협력 이웃 노드 수와 최소 컨센서스 달성 시간을 보여준다. 참여 노드 수가 작을 때는 최적 이웃 노드 수가 선형적으로 증가하다가 어느 이상이 되면 일정한 값으로 수렴하게 된다. 즉, 네트워크의 규모가 작아 컨센서스에 참여하는 노드 수가 적을 때에는 정보 교환 지연을 줄이는 것보다는 알고리즘의 반복 횟수를 줄이는 것이 성능에 더 좋은 영향을 미침을 알 수 있다. 따라서 네트워크 규모가 작을 때에는 모든 노드가 협력하는 것이 컨센서스 달성 시간을 줄이는 최적 전략이 된다. 반대로 어느 이상으로 참여 노드 수가 증가하면 정보 교환 지연 효과가 전체 성능에 더 크게 작용하여 이웃 노드 수를 적절히 제한하는 것이 컨센서스 달성 시간을 줄이는데 유리하다. 따라서 네트워크 규모가 커짐에 따라 컨센서스 달성 시간을 최소화하는 최적 이웃 노드 수가 존재하므로 컨센서스 알고리즘 동작시 협력 이웃 노드 수를 적절히 제한하는 것이 최적 전략이 된다. 아울러 주목할 만한 점은 참여 단말 수가 어느 이상으로 증가하면 참여 단말 수에 상관없이 최적의 이웃 노드 수는 일정한 값으로 수렴한다는 점이다. 이때 최적 이웃 노드 수는 접속 제어 확률 p 에만 의존하는데, p 값이 커질수록 단말의 접속 시도 확률이 증가하여 더 큰 지연이 발생하므로 이웃 노드 수를 줄이는 것이 성능에 좋다. 또한 최적 이웃 단말 수를 적용할 때 얻는 최소 컨센서스 달성 시간은 참여 노드 수와 p 값이 커질수록 증가하게 된다. 이와 같은 결과를 바탕으로 네트워크 규모에 따라 컨센서스 달성 시간을 최소화하기 위해서는 협력하는 이웃 노드 수를 적절히 결정하는 송신 노드 커버리지 제어 또는 송신전력 제어와 같은 알고리즘이 필요하다.
PPT Slide
Lager Image
참여 노드 수에 따른 (a) 최적 협력 이웃 노드 수와 (b) 최소 컨센서스 달성 시간 Fig. 4 (a) optimal number of neighbors and (b) minimum consensus time versus number of participating nodes
Ⅴ. 결 론
본 논문에서는 CSMA/CA 기반의 분산 무선 네트워크에서 컨센서스 알고리즘을 동작시킬 때 발생하는 트레이드오프 성능에 대해서 분석하였다. 컨센서스 알고리즘은 협력 이웃 노드가 많을수록 빠른 수렴 속도를 갖지만, 무선 네트워크상에서는 협력 이웃 노드가 많을수록 접속 충돌로 인하여 전송 지연이 증가한다. 따라서 두 성능 간에 트레이드오프가 존재하며, 이로 인하여 컨센서스 달성 시간을 최소화하는 최적 이웃 노드 수가 존재한다. 최적 이웃 노드 수를 분석해본 결과, 컨센서스 참여 노드 수가 적을 때에는 모든 노드가 다같이 협력하는 것이 최적 운용 전략이 되지만, 참여 노드 수가 임계 값 이상으로 증가할 경우에는 이웃 노드 수를 일정 값으로 고정시키는 것이 최적 전략이 됨을 알 수 있었다. 이러한 결과를 바탕으로 추후에는 컨센서스 달성 시간 최소화를 위한 송신 노드 커버리지 제어 및 송신전력 제어에 대한 연구를 수행할 예정이다.
Acknowledgements
이 논문은 2013년도 정부(교육과학기술부)의 재원으로 한국연구재단의 기초연구사업 지원을 받아 수행된 것임(2011-0025424). 본 연구는 미래창조과학부가 지원한 2013년 정보통신·방송(ICT) 연구개발사업의 연구결과로 수행되었음.
BIO
최현호(Hyun-Ho Choi)
2001년 2월: KAIST 전기및전자공학과 공학사
2003년 2월: KAIST 전기및전자공학과 공학석사
2007년 2월: KAIST 전기및전자공학과 공학박사
2007년 3월 ~ 2011년 2월: 삼성종합기술원 전문연구원
2011년 3월 ~ 현재: 국립한경대학교 전기전자제어공학과 조교수
※관심분야 : 매체접속제어, 분산자원관리, 저전력 프로토콜, 생체모방 알고리즘, 차세대 이동통신 시스템
References
Olfati-Saber R. , Fax J. , Murray R. 2007 "Consensus and Cooperation in Networked Multi-Agent Systems," Proceedings of the IEEE http://dx.doi.org/10.1109/JPROC.2006.887293 95 (1) 215 - 233    DOI : 10.1109/JPROC.2006.887293
Hong Y.-W. , Scaglione A. 2005 “A Scalable Synchronization Protocol for Large Scale Sensor Networks and Its Applications,” IEEE Journal on Selected Areas in Communications http://dx.doi.org/10.1109/JSAC.2005.845418 23 (5) 1085 - 1099    DOI : 10.1109/JSAC.2005.845418
Yoo H.-J. , Lee M.-N. , Cho Y.-S. 2012 “A Distributed Frequency Synchronization Technique for OFDMA-Based Mesh Networks Using Bio-Inspired Algorithm,” J. Korean Inst. Commun. Inform. Soc. (KICS) http://dx.doi.org/10.7840/kics.2012.37B.11.1022 37B (11) 1022 - 1032    DOI : 10.7840/kics.2012.37B.11.1022
Pagliari R. , Hong Y. P. , Scaglione A. 2010 "Bio-inspired Algorithms for Decentralized Round-Robin and Proportional Fair Scheduling," IEEE Journal on Selected Areas in Communications http://dx.doi.org/10.1109/JSAC.2010.100506 28 (4) 564 - 575    DOI : 10.1109/JSAC.2010.100506
Olfati-Saber R. 2005 “Ultrafast Consensus in Small-World Networks,” Proceeding of American Control Conference 2371 - 2378
Olfati-Saber R. , Shamma J. S. 2005 “Consensus Filters for Sensor Networks and Distributed Sensor Fusion,” Proceeding of IEEE Conf. Decision and Control and Eur. Control Conf. (CDC-ECC ’05) 6698 - 6703
Choi H.-H. 2014 "Performance Evaluation of Biologically Inspired Consensus Algorithm in Distributed Wireless Networks," KICS Joint Conference on Communications and Information (JCCI) 1 - 2
Saber R. O. , Murray R. M. 2003 “Consensus protocols for networks of dynamic agents,” Proceeding of American Control Conference 951 - 956
Olfati-Saber R. , Murray R. M. 2004 “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Trans. Autom. Control http://dx.doi.org/10.1109/TAC.2004.834113 49 (9) 1520 - 1533    DOI : 10.1109/TAC.2004.834113
Choi H.-H. , Moon J.-M. , Lee I.-H. , Lee H. 2013 "Carrier Sense Multiple Access with Collision Resolution," IEEE Communications Letters http://dx.doi.org/10.1109/LCOMM.2013.020413.122318 17 (6) 1284 - 1287    DOI : 10.1109/LCOMM.2013.020413.122318
MacKenzie R. , O’Farrell T. 2010 "Throughput and Delay Analysis for p-Persistent CSMA with Heterogeneous Traffic," IEEE Trans. Commun. http://dx.doi.org/10.1109/TCOMM.2010.082710.090523 58 2881 - 2891    DOI : 10.1109/TCOMM.2010.082710.090523
2007 Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications IEEE
Choi H.-H. , Lee J.-R. 2014 "Distributed Transmit Power Control for Maximizing End-to-End Throughput in Wireless Multi-hop Networks," Springer Wireless Personal Communications http://dx.doi.org/10.1007/s11277-013-1342-2 74 (3) 1033 - 1044    DOI : 10.1007/s11277-013-1342-2