Journal of the Korea Institute of Information and Communication Engineering 최현호 * Tradeoff Analysis of Consensus Algorithm in Disibuted Wireless Networks Hyun-Ho Choi * Department of Elecical, Eleconic and Conol Engineering, Institute for Information Technology Convergence, Hankyong National University, Anseong 456-749, Korea 요약 본논문에서는 CSMA/CA 기반의분산무선네트워크에컨센서스알고리즘을적용할때발생하는트레이드오프성능을분석한다. 컨센서스알고리즘자체는협력이웃노드가많을수록빠른수렴속도를갖지만, 무선네트워크상에서는협력이웃노드가많을수록접속충돌로인하여전송지연이증가한다. 따라서두성능간에트레이드오프가존재하며, 이로인하여컨센서스달성시간을최소화하는최적의협력이웃노드수가존재한다. 시뮬레이션을통하여컨센서스참여노드수에따라최적이웃노드수를도출한결과, 네트워크규모가작을때에는모든노드가다같이협력하는것이최적이지만네트워크규모가어느이상으로커질경우에는이웃노드수를일정값으로제한하는것이최적운용전략이된다. ABSTRACT In this paper, we analyze the adeoff performance of a consensus algorithm when it is applied to the CSMA/CA-based disibuted wireless network. The consensus algorithm has a faster convergence speed as the number of cooperating neighbors increases, but the ansmission delay on the wireless network increases due to access collisions as the number of cooperating neighbors increases. Therefore, there exists a adeoff relationship between these two performances and so there exists an optimal number of cooperating neighbors that minimizes the consensus time. The result for the optimal number of neighbors according to the number of nodes that participate in the consensus shows that it is optimal for all nodes to cooperate together in the small-scale network but it is optimal to limit the number of neighbors to a fixed value in the large-scale network with nodes greater than a certain value. 키워드 : 컨센서스, 매체접속제어, 분산네트워크, 트레이드오프분석 Key word : Consensus, Medium access conol, Disibuted network, Tradeoff analysis 접수일자 : 4. 4. 심사완료일자 : 4. 4. 4 게재확정일자 : 4. 4. 29 * Corresponding Author Hyun-Ho Choi(E-mail:hhchoi@hknu.ac.kr, Tel:+82-3-67-5297) Department of Elecical, Eleconic and Conol Engineering, Institute for Information Technology Convergence, Hankyong National University, Anseong 456-749, Korea Open Access http://dx.doi.org/.69/jkiice.4.8.5.8 print ISSN: 2234-4772 online ISSN: 2288-465 This is an Open Access article disibuted under the terms of the Creative Commons Atibution Non-Commercial License(http://creativecommons.org/li-censes/ by-nc/3./) which permits unresicted non-commercial use, disibution, and reproduction in any medium, provided the original work is properly cited. Copyright C The Korea Institute of Information and Communication Engineering.
Ⅰ. 서론컨센서스 (consensus) 란각노드의상태에의존하는어떠한값이서로일치하게됨을의미하며, 컨센서스알고리즘은컨센서스를위해각노드가네트워크상의이웃노드들과관련정보를공유하는상호규칙을일컫는다 []. 컨센서스알고리즘은분산시간및주파수동기화 [2, 3], 분산공평 (round-robin) 자원할당 [4], 빠른분산데이터공유 [5], 센싱정보의분산퓨전 [6] 등컨센서스가필요한다양한통신네트워크응용분야에접목되어사용되어왔다. 이때관심을갖는성능지표는얼마나빨리컨센서스를달성할수있느냐에관한것으로, 이는컨센서스알고리즘의제어파라미터와네트워크환경에영향을받는다 [7]. 하지만지금까지의컨센서스관련연구는알고리즘자체의수렴여부와수렴속도에중점을두었지실제네트워크환경에서노드간상태정보교환에의해발생하는전송지연에대해서는고려하지않았다 [, 8, 9]. 컨센서스알고리즘자체의수렴속도는일반적으로노드간정보공유가많을수록, 즉노드당이웃노드수가많을수록빨라진다. 따라서컨센서스를이루고하하는네트워크상의모든노드들이다같이협력하는것이컨센서스를달성하는데걸리는시간을최소화하는이상적인방법이된다 [8, 9]. 하지만컨센서스알고리즘이수행되는실제네트워크환경을고려하면상호정보교환을수행하는이웃노드수가증가할수록전송지연이증가하고협력오버헤드가커지므로전체적인컨센서스알고리즘의성능에이들요소를고려해야한다. 특히컨센서스알고리즘은주로분산네트워크환경에서중앙의제어없이노드간정보공유가이루어지므로이웃노드수의증가는전송패킷의충돌로인하여전송지연의급격한증가를야기한다 []. 따라서실제무선네트워크환경에서컨센서스알고리즘은정보를공유하는이웃노드수에따라트레이드오프 (adeoff) 성능이존재함을알수있다. 즉, 협력하는이웃노드수가증가함에따라알고리즘의수렴속도는빨라지지만노드간정보교환에따른전송지연의증가로인하여알고리즘동작시간이증가한다. 본논문에서는가장일반적인 CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance) 프로토콜을사용하는분산무선네트워크환경에서주어진 노드들이컨센서스를달성하고자할때, 노드당협력이웃노드수에따른컨센서스의성능변화를살펴본다. 이를기반으로전체참여노드수에따라컨센서스달성시간을최소화하기위한최적파라미터를도출하고, 분산무선네트워크환경에서최적컨센서스프로토콜의운용방법을제시한다. 본논문의구성은다음과같다. Ⅱ장에서는본논문에서고려하는컨센서스알고리즘을소개하고수렴특성을설명한다. Ⅲ장에서는 CSMA/CA 프로토콜을사용하는분산무선네트워크에서패킷전송지연을수학적으로도출하고컨센서스달성시간으로의영향을분석한다. Ⅳ장에서는시뮬레이션결과를도출하고트레이드오프성능및최적화방안에대해서고찰한다. 마지막으로 Ⅴ장에서본논문에대한결론을맺는다. Ⅱ. 컨센서스알고리즘 컨센서스알고리즘은연속 / 이산시간에따라, 수신한주변이웃노드들의상태값의처리방식에따라몇가지변형된형태가존재하는데, 본논문에서는다음식으로표현되는이산시간기반의컨센서스알고리즘을고려한다 []. x i( k + ) xi ( k) + x j ( k) + N () i j N i 여기에서 x i (k) 는 k시간에노드 i의상태값, N i 는노드 i와통신가능한이웃노드의집합을나타내고, N i 는노드 i의이웃노드의개수를나타낸다. 이컨센서스알고리즘에따르면각노드는현재자신과이웃노드들의상태값의평균으로다음상태값을결정한다. 즉, 각노드는주변이웃노드들의상태정보만을가지고분산적으로지역적인평균 (local average) 을취한다. 이와같은반복동작은수행횟수가증가함에따라모든노드의상태값이동일한값으로수렴하게되는 ( 즉, x i x j i,j) 컨센서스를이루게된다. 또한식 () 은다음과같은행렬연산형태로표현가능하다 []. 8
x( k + ) ( I + D) ( I + ) x( k) A x( k) (2) 전체참여노드수가 N이라고할때 I는 NⅹN 단위행렬이며, D는주대각성분이각노드의이웃노드개수인대각행렬이며, A는 i, j 노드간연결성을나타내는인접행렬 (adjacency maix) 이다. 이때페론 (erron) 이라불리는행렬 는 (I+D) - (I+A) 로정의되는데, 이론적으로행렬 의두번째로큰고유값이작을수록컨센서스알고리즘의수렴이빠르다는사실이밝혀져있다 [, 8]. 이와같이지금까지연구된컨센서스이론은컨센서스알고리즘의수렴여부및수렴속도의경향성은알려주지만, 실제컨센서스가달성되기까지걸리는시간은계산해주지못한다. 따라서본논문에서는식 () 의컨센서스알고리즘의수렴여부와수렴속도에대한이론적결과를바탕으로노드간연결토폴로지와노드별상태값분포등의다양한환경변수를반영한시뮬레이션을통하여컨센서스달성시간을구한다. ) N i ( p (3) 또한패킷의전송성공확률 s 와전송이없는채널휴지시간 T idle 은각각아래와같이계산된다. p ( p) s T idle p( p) ( p) Ts k( ) k Ts N ( p) i k p( p) Ts (4) (5) 여기에서 T s 는단위타임슬롯의길이를나타낸다. 패킷이성공적으로전달될때까지재전송을수행한다고가정하면 N i 의노드가경쟁할때발생하는평균패킷지연은다음과같은계산된다. Ⅲ. 분산무선네트워크에서의컨센서스알고리즘의성능분석 컨센서스알고리즘은노드간상태정보의교환을필요로하므로이를네트워크상에서수행할때노드간패킷전송지연이발생하게된다. 고려하는분산무선네트워크에서는 CSMA/CA의사용을가정하여컨센서스알고리즘동작시발생할수있는패킷전송지연을도출하고컨센서스달성시간에반영한다. 본논문에서는경쟁노드수에따라접속확률을쉽게제어할수있는 p-persistent CSMA 방식을고려한다 []. CSMA/CA 프로토콜에서하나의채널을통해모든노드가 p의확률로패킷을전송하고자할때발생하는평균전송지연을구하고자한다. 먼저노드 i의이웃노드수를 N i 라하고이들이웃노드들이노드 i로상태정보가담긴패킷을 p-persistent CSMA 방식으로전송한다고할때, 현재타임슬롯에서한명이라도접속을시도할확률 은다음과같다. D k( T k Tidle + T s idle data + T data )( ) k s s 여기에서 T data 는전송하는패킷데이터의시간길이를나타낸다. 컨센서스알고리즘의동작을위해서는네트워크상의모든노드들이각자자신의주변노드들과상태정보를교환해야한다. 이때각노드들은자신의정보를주변이웃노드에게매번유니캐스트로전송하는것이아니라그림 과같이지역적인브로드캐스트를수행하게된다. 따라서한노드의한번의전송성공은브로드캐스트전송의성공을의미하고, 이에따라주변이웃노드들은이노드에대한정보를성공적으로수신하게된다. 이와같은맥락에서각노드가주변이웃노드들과의경쟁에서성공하게될때까지의시간지연은한번의성공적인채널접속에소요되는시간이되며, 경쟁하는이웃노드들모두가이를이뤄야하므로서로정보를교환하는데걸리는시간은이웃노드수에비례하 (6) 82
여선형적으로증가하게된다. 전체네트워크상에서모든노드들이동시다발적으로이러한방식으로패킷을교환한다고보면평균이웃노드수가 N i 이고평균패킷 지연이 D 일때, 모든노드들이서로패킷을교환하는데걸리는시간은점근적으로 (asymptotically) N i D 가된다. Broadcast area Broadcast area 2 값이 -2 보다작은경우로결정하였다 [3]. 시뮬레이션은 MATLAB을사용하여수행하였다. 표. 시뮬레이션파라미터 Table. Simulation arameters Name Value ersistent probability (p).3~.5 Duration of time slot (T s ) 9 μs Transmitted packet size 64 byte Transmission rate 6 Mb/s Transmitted data duration (T data ) 85.3 μs Network topology Regular network Number of participating nodes (N) ~5 State value of each node Uniform(,) Convergence condition x(k)-x( ) < -2 Broadcast area 3 그림. 분산무선네트워크에서컨센서스알고리즘을위한지역적인브로드캐스트의개념 Fig. A concept of local broadcast for consensus algorithm in the disibuted wireless network 그림 2는참여노드수 N이고각노드의평균이웃노드수 (N i ) 를각각 6명과 명으로설정하였을때알고리즘의반복횟수에따른각노드의상태값의변화를보여준다. 컨센서스알고리즘이반복됨에따라처음에다르게분포되어있던노드의상태값은하나의값으로수렴하게된다. 즉컨센서스를이루게된다. 이때상태정보를교환하는협력이웃노드수를증가시킬경우수렴속도가매우빨라짐을확인할수있다. 따라서최종적으로컨센서스달성에걸리는시간 (T consensus ) 은시뮬레이션을통해구한수렴에필요한알고리즘의반복횟수 (N i ) 와패킷교환지연값 (N i D) 의곱으로다음과같이결정된다. 9 8 (a) 9 8 (b) 7 7 Tconsensus D (7) State value (x) 6 5 4 State value (x) 6 5 4 Ⅳ. 시뮬레이션결과및고찰 3 3 표 은사용한시뮬레이션파라미터를보여준다. 전송관련파라미터는 IEEE 82. 표준의 OFDM 모드의값을참고하였고 [2], 네트워크토폴로지는간단한정규 (regular) 네트워크 [] 를가정하여각노드별이웃노드수를동일하게증가시켜가며성능을보았다. 초기에각노드의상태값은 ~ 사이에서균일하게결정되며, 컨센서스알고리즘의수렴조건은모든노드의현재상태값과이론적인수렴값의차이벡터의 2-norm 5 5 Iterations 5 5 Iterations 그림 2. 알고리즘의반복횟수에따른각노드의상태값의변화 (a) 이웃노드수 N i6, (b) 이웃노드수 N i ( 참여노드수 N 일때 ) Fig. 2 Evolution of state value of each node (x i) versus number of iterations: (a) number of neighbors N i6 and (b) number of neighbors N i (when number of participating nodes N) 83
Number of iterations Average delay (s) Consensus time (s) 3 (a) 4 6 8 Number of neighbors (b).4.3.2. 4 6 8 Number of neighbors (c).5.5 36 4 6 8 Number of neighbors 그림 3. 협력이웃노드수에따른 (a) 수렴을위한컨센서스알고리즘의반복횟수, (b) 평균정보교환지연, (c) 컨센서스달성시간 (N, p.5 일때 ) Fig. 3 (a) number of iterations for convergence, (b) average information sharing delay, and (c) consensus time versus number of neighbors (when N, p.5) 그림 3은참여노드수가 이고접속제어확률값이.5일때협력이웃노드수의증가에따른컨센서스알고리즘의반복횟수, 평균정보교환지연, 컨센서스달성시간을순서대로보여준다. 이웃노드수가증가할수록알고리즘의반복횟수는기하급수적으로줄어들지만노드간정보교환지연은기하급수적으로증가한다. 즉, 컨센서스수렴속도와네트워크에서발생하는정보교환지연간에는트레이드오프가존재한다. 따라서이두성능의곱으로결정되는컨센서스달성시간을보면아래로볼록한형태가되며, 이경우이웃 노드수가 36일때가장빠르게컨센서스를달성함을알수있다. 즉, 주어진환경변수에따라최적의협력이웃노드수를찾음으로써컨센서스달성시간을최소화할수있다. Optimal number of neighbors Minimum consensus time (s) 4 8 6 4 (a) p.3 p.5 p.7 p.9 3 4 5 Number of nodes (N) 25 5 5 p.3 p.5 p.7 p.9 (b) 3 4 5 Number of nodes (N) 그림 4. 참여노드수에따른 (a) 최적협력이웃노드수와 (b) 최소컨센서스달성시간 Fig. 4 (a) optimal number of neighbors and (b) minimum consensus time versus number of participating nodes 그림 4는컨센서스에참여하는전체노드수에따른최적협력이웃노드수와최소컨센서스달성시간을보여준다. 참여노드수가작을때는최적이웃노드수가선형적으로증가하다가어느이상이되면일정한값으로수렴하게된다. 즉, 네트워크의규모가작아컨센서스에참여하는노드수가적을때에는정보교환지연을줄이는것보다는알고리즘의반복횟수를줄이는 84
것이성능에더좋은영향을미침을알수있다. 따라서네트워크규모가작을때에는모든노드가협력하는것이컨센서스달성시간을줄이는최적전략이된다. 반대로어느이상으로참여노드수가증가하면정보교환지연효과가전체성능에더크게작용하여이웃노드수를적절히제한하는것이컨센서스달성시간을줄이는데유리하다. 따라서네트워크규모가커짐에따라컨센서스달성시간을최소화하는최적이웃노드수가존재하므로컨센서스알고리즘동작시협력이웃노드수를적절히제한하는것이최적전략이된다. 아울러주목할만한점은참여단말수가어느이상으로증가하면참여단말수에상관없이최적의이웃노드수는일정한값으로수렴한다는점이다. 이때최적이웃노드수는접속제어확률 p에만의존하는데, p 값이커질수록단말의접속시도확률이증가하여더큰지연이발생하므로이웃노드수를줄이는것이성능에좋다. 또한최적이웃단말수를적용할때얻는최소컨센서스달성시간은참여노드수와 p 값이커질수록증가하게된다. 이와같은결과를바탕으로네트워크규모에따라컨센서스달성시간을최소화하기위해서는협력하는이웃노드수를적절히결정하는송신노드커버리지제어또는송신전력제어와같은알고리즘이필요하다. Ⅴ. 결론본논문에서는 CSMA/CA 기반의분산무선네트워크에서컨센서스알고리즘을동작시킬때발생하는트레이드오프성능에대해서분석하였다. 컨센서스알고리즘은협력이웃노드가많을수록빠른수렴속도를갖지만, 무선네트워크상에서는협력이웃노드가많을수록접속충돌로인하여전송지연이증가한다. 따라서두성능간에트레이드오프가존재하며, 이로인하여컨센서스달성시간을최소화하는최적이웃노드수가존재한다. 최적이웃노드수를분석해본결과, 컨센서스참여노드수가적을때에는모든노드가다같이협력하는것이최적운용전략이되지만, 참여노드수가임계값이상으로증가할경우에는이웃노드수를일정값으로고정시키는것이최적전략이됨을알수있었다. 이러한결과를바탕으로추후에는컨센 서스달성시간최소화를위한송신노드커버리지제어및송신전력제어에대한연구를수행할예정이다. 감사의글이논문은 3년도정부 ( 교육과학기술부 ) 의재원으로한국연구재단의기초연구사업지원을받아수행된것임 (-25424). 본연구는미래창조과학부가지원한 3년정보통신 방송 (ICT) 연구개발사업의연구결과로수행되었음. REFERENCES [ ] R. Olfati-Saber, J. Fax, and R. Murray, "Consensus and Cooperation in Networked Multi-Agent Systems," roceedings of the IEEE, vol. 95, no., pp. 25-233, Jan. 7. [ 2 ] Y.-W. Hong and A. Scaglione, A Scalable Synchronization rotocol for Large Scale Sensor Networks and Its Applications, IEEE Journal on Selected Areas in Communications, vol. 23, no. 5, pp. 85-99, May 5. [ 3 ] H.-J. Yoo, M.-N. Lee, and Y.-S. Cho, A Disibuted Frequency Synchronization Technique for OFDMA-Based Mesh Networks Using Bio-Inspired Algorithm, J. Korean Inst. Commun. Inform. Soc. (KICS), vol.37b, no., pp 22-32, Nov. 2. [ 4 ] R. agliari, Y.. Hong, and A. Scaglione, "Bio-inspired Algorithms for Decenalized Round-Robin and roportional Fair Scheduling," IEEE Journal on Selected Areas in Communications, vol. 28, no. 4, pp. 564-575, May. [ 5 ] R. Olfati-Saber, Ulafast Consensus in Small-World Networks, in roceeding of American Conol Conference, pp. 237 2378, Jun. 5. [ 6 ] R. Olfati-Saber and J. S. Shamma, Consensus Filters for Sensor Networks and Disibuted Sensor Fusion, in roceeding of IEEE Conf. Decision and Conol and Eur. Conol Conf. (CDC-ECC 5), pp. 6698 673, Dec. 5. [ 7 ] H.-H. Choi, "erformance Evaluation of Biologically Inspired Consensus Algorithm in Disibuted Wireless Networks," KICS Joint Conference on Communications and Information (JCCI), pp. -2, Apr. 4. 85
[ 8 ] R. O. Saber and R. M. Murray, Consensus protocols for networks of dynamic agents, in roceeding of American Conol Conference, pp. 95 956, 3. [ 9 ] R. Olfati-Saber and R. M. Murray, Consensus problems in networks of agents with switching topology and time-delays, IEEE Trans. Autom. Conol, vol. 49, no. 9, pp. 5 533, Sep. 4. [] H.-H. Choi, J.-M. Moon, I.-H. Lee, and H. Lee "Carrier Sense Multiple Access with Collision Resolution," IEEE Communications Letters, vol. 7, no. 6, pp. 284-287, June 3. [] R. MacKenzie, T. O Farrell, "Throughput and Delay Analysis for p-ersistent CSMA with Heterogeneous Traffic," IEEE Trans. Commun., vol. 58, pp. 288-289, Oct.. [2] IEEE Std 82.-7: art : Wireless LAN Medium Access Conol (MAC) and hysical Layer (HY) Specifications, IEEE, 7. [3] H.-H. Choi and J.-R. Lee, "Disibuted Transmit ower Conol for Maximizing End-to-End Throughput in Wireless Multi-hop Networks," Springer Wireless ersonal Communications, vol. 74, no. 3, pp. 33-44, Feb. 4. 최현호 (Hyun-Ho Choi) 년 2 월 : KAIST 전기및전자공학과공학사 3 년 2 월 : KAIST 전기및전자공학과공학석사 7 년 2 월 : KAIST 전기및전자공학과공학박사 7 년 3 월 ~ 년 2 월 : 삼성종합기술원전문연구원 년 3 월 ~ 현재 : 국립한경대학교전기전자제어공학과조교수 관심분야 : 매체접속제어, 분산자원관리, 저전력프로토콜, 생체모방알고리즘, 차세대이동통신시스템 86