송태원
(Korea University School of Electrical Engineering)
,
박현희
(INRIA French Institute for Research in Computer Science and Control)
,
백상헌
(Korea University School of Electrical Engineering)
무선 애드혹 네트워크에서 이웃 탐색 과정은 네트워크를 초기화하는데 먼저 수행되어야 하고, 라우팅 알고리즘이나 토폴로지 컨트롤, 그리고 MAC 계층 설계를 위해서도 반드시 필요한 과정이므로 효율적인 분산적 이웃 탐색방법 설계가 필수적이다. 본 논문에서는 확률적 이웃 탐색 기법 (PND: Probabilistic neighbor discovery)을 제안한다. 제안한 기법에서는 MIMD (Multiplicative-increase, multiplicative-decrease) 정책을 통해 광고 메시지의 전송확률을 제어함으로써 이웃 탐색에 소요되는 시간을 줄이는 것이 가능하다. 더불어 임의의 기기가 광고 메시지를 전송한 경우, 그 메시지가 성공적으로 전송되었는지 여부를 알 수 있는 충돌 감지 기법 (CD: Collision detection)을 도입함으로써 확률적 이웃 탐색 기법의 성능을 더 높일 수 있다. 시뮬레이션 결과는 제안 기법이 모든 이웃을 탐색하기까지 소요되는 시간을 15.6%~57%까지 감소시킬 수 있음을 보여준다.
무선 애드혹 네트워크에서 이웃 탐색 과정은 네트워크를 초기화하는데 먼저 수행되어야 하고, 라우팅 알고리즘이나 토폴로지 컨트롤, 그리고 MAC 계층 설계를 위해서도 반드시 필요한 과정이므로 효율적인 분산적 이웃 탐색방법 설계가 필수적이다. 본 논문에서는 확률적 이웃 탐색 기법 (PND: Probabilistic neighbor discovery)을 제안한다. 제안한 기법에서는 MIMD (Multiplicative-increase, multiplicative-decrease) 정책을 통해 광고 메시지의 전송확률을 제어함으로써 이웃 탐색에 소요되는 시간을 줄이는 것이 가능하다. 더불어 임의의 기기가 광고 메시지를 전송한 경우, 그 메시지가 성공적으로 전송되었는지 여부를 알 수 있는 충돌 감지 기법 (CD: Collision detection)을 도입함으로써 확률적 이웃 탐색 기법의 성능을 더 높일 수 있다. 시뮬레이션 결과는 제안 기법이 모든 이웃을 탐색하기까지 소요되는 시간을 15.6%~57%까지 감소시킬 수 있음을 보여준다.
In wireless ad hoc networks, neighbor discovery is essential in the network initialization and the design of routing, topology control, and medium access control algorithms. Therefore, efficient neighbor discovery algorithms should be devised for self-organization in wireless ad hoc networks. In thi...
In wireless ad hoc networks, neighbor discovery is essential in the network initialization and the design of routing, topology control, and medium access control algorithms. Therefore, efficient neighbor discovery algorithms should be devised for self-organization in wireless ad hoc networks. In this paper, we propose a probabilistic neighbor discovery (PND) algorithm, which aims at reducing the neighbor discovery time by adjusting the transmission probability of advertisement messages through the multiplicative-increase/multiplicative-decrease (MIMD) policy. To further improve PND, we consider the collision detection (CD) capability in which a device can distinguish between successful reception and collision of advertisement messages. Simulation results show that the transmission probabilities of PND and PND with CD converge on the optimal value quickly although the number of devices is unknown. As a result, PND and PND with CD can reduce the neighbor discovery time by 15.6% to 57.0% compared with the ALOHA-like neighbor discovery algorithm.
In wireless ad hoc networks, neighbor discovery is essential in the network initialization and the design of routing, topology control, and medium access control algorithms. Therefore, efficient neighbor discovery algorithms should be devised for self-organization in wireless ad hoc networks. In this paper, we propose a probabilistic neighbor discovery (PND) algorithm, which aims at reducing the neighbor discovery time by adjusting the transmission probability of advertisement messages through the multiplicative-increase/multiplicative-decrease (MIMD) policy. To further improve PND, we consider the collision detection (CD) capability in which a device can distinguish between successful reception and collision of advertisement messages. Simulation results show that the transmission probabilities of PND and PND with CD converge on the optimal value quickly although the number of devices is unknown. As a result, PND and PND with CD can reduce the neighbor discovery time by 15.6% to 57.0% compared with the ALOHA-like neighbor discovery algorithm.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 확률적 이웃 탐색 기법 (PND:Probabilistic neighbor discovery)을 제안한다. 본 기법은 MIMD (Multiplicative-increase, multiplicative-decrease) 정책을 통해 광고 메시지의 전송 확률을 제어함으로써 이웃 탐색에 소요되는 시간을 줄이는 것을 목표로 하고 있다.
본 논문에서는 확률적 이웃 탐색 기법 (PND:Probabilistic neighbor discovery)을 제안한다. 본 기법은 MIMD (Multiplicative-increase, multiplicative-decrease) 정책을 통해 광고 메시지의 전송 확률을 제어함으로써 이웃 탐색에 소요되는 시간을 줄이는 것을 목표로 하고 있다. 각 기기는 임의의 확률로 자신의 ID와 자신의 전송 확률을 포함한 광고 메시지를 전송한다.
우리는 본 논문에서 확률적 이웃 탐색 기법, 즉 PND 기법을 제안하였다. PND 기법은 이웃 탐색 과정 시, 광고 전송 결과에 따라 다음 시간의 광고 메시지 전송 확률을 분산적이고 자율적으로 조정함으로써 네트워크에 존재하는 기기의 수를 알지 못하는 상황에서도 효과적으로 이웃 탐색 과정을 수행할 수 있다.
가설 설정
. 상기 방법들은 모두 사전에 모든 기기들이 네트워크에 존재하는 기기의 수를 알고 있다고 가정하고 있다. 하지만 무선 애드혹 네트워크에서와 같은 분산적인 환경에서는 네트워크에 존재하는 기기의 수를 미리 알기 힘들다.
본 기법에서는 slotted-ALOHA 프로토콜을 기반으로 한 매체 접근 제어 프로토콜을 가정한다. Slotted-ALOHA 프로토콜에서는 시간이 슬롯으로 나뉘어져 있고 각 시간 슬롯의 시작점에서만 전송을 시도할 수 있다.
Slotted-ALOHA 프로토콜에서는 시간이 슬롯으로 나뉘어져 있고 각 시간 슬롯의 시작점에서만 전송을 시도할 수 있다. 또한 slotted-ALOHA 프로토콜은 단방향 통신만을 지원한다고 가정하였다. 즉, 모든 기기는 메시지를 송신하고 있는 중이라면 어떠한 메시지도 수신할 수 없게 된다.
이러한 충돌 감지 기법을 통해 이웃 탐색에 소요되는 시간을 줄일 수 있고, 본 논문에서는 PND 기법에 충돌 감지 기법을 적용했을 때와 적용하지 않았을 때 모두 고려하였다. 네트워크에 존재하는 기기들은 고정된 위치를 지니고 있으며 각자 고유한 ID를 가지고 있다고 가정한다. 광고 메시지를 전송할 경우 그 메시지에는 기기의 고유 ID와 전송 확률이 포함되어 그 메시지를 수신한 다른 기기들은 어떠한 확률을 통해 전송된 메시지인지 파악할 수 있고, 어떤 기기가 전송하였는지 알 수 있다.
첫 번째 비교 기법은 균등확률기법(EP:Equal probability)이다. 균등확률기법에서는 각 기기가 자신의 전송 범위에 존재하는 기기의 수를 모두 알고 있다고 가정하고, 전송 확률은 slotted-ALOHA의 최적 값으로 알려진 1/N, 즉 존재하는 기기의 수의 역수의 확률을 유지한다.
제안 방법
[6]는 지향성 안테나를 활용한 이웃 탐색 기법을 제시하였다. 그러나 주어진 시간 안에 k개의 이웃, 즉 k-connectivity만을 보장할 수 있는 제한된 알고리즘을 제시하였다. [7]에서는 빠른 이동성 환경에서의 이웃 탐색 기법을 제안하였으나 네트워크에 존재하는 기기의 수에 대한 고려를 하지 않았다.
각 기기는 임의의 확률로 자신의 ID와 자신의 전송 확률을 포함한 광고 메시지를 전송한다. 그리고 광고 메시지 전송의 결과, 즉 송신시도, 수신성공, 수신실패, 그리고 채널이 사용되지 않은 상황에 따라 적응적으로 전송 확률을 조정한다. 그러므로 본 기법에서는 네트워크의 기기 수를 알지 못해도 시간이 흐름에 따라 최적의 전송 확률로 수렴해 가며, 이웃 탐색에 소요되는 시간을 줄일 수 있다.
네 번째 시간 슬롯에서는 기기 2만이 광고 메시지 전송을 시도하였다. 전송을 시도한 기기 2는 전송 확률을 바꾸지 않으며, 이를 성공적으로 수신한 기기 1, 3, 4는 자신의 광고 메시지 전송 확률을 기기 2의 전송 확률이었던 0.
그림 2는 최초 전송 확률의 변화에 따른 이웃 탐색 소요 시간을 나타낸 그림이다. 초기 전송 확률을 0과 0.5 사이의 임의의 값을 설정하게 한 경우와, 1/N, 즉 기기 수의 역수로 지정하게 한 경우를 비교하였다. 두 경우에 대해 상당한 차이가 나타나지는 않은 모습을 관찰할 수 있는데, 이것은 초기 전송 확률이 어떻게 부여되건 몇 번의 이웃 탐색이 이루어지면서 최적값에 빠르게 수렴하기 때문이다.
그림 6에서는 다양한 멀티홉 환경에서 PND 기법의 성능이 어떤 추이를 보이는지 나타내었다. 가능한 멀티홉 환경 중에서 대표적으로 Linear, Dumbbell, 그리고 Fullmesh 구조를 선택하여 시뮬레이션을 수행하였다. Linear 구조에서는 기기가 일렬로 나열되어 있으며 임의의 기기의 전송범위는 양 옆의 기기, 즉 두 기기까지 도달할 수 있는 환경을 의미한다.
데이터처리
기본 PND와 충돌 감지 기능이 적용된 PND의 성능을 분석하기 위해 MATLAB 프로그램을 사용하였다. 모든 이웃 탐색 과정은 모든 기기가 성공적으로 광고 메시지를 전송하였을 경우 종료되며, 신뢰성 있는 시뮬레이션 결과 도출을 위해 모든 결과값은 1000번씩 시행된 결과의 평균값을 의미한다.
제안하는 PND는 두 가지 기법과의 비교를 통해 분석되었다. 첫 번째 비교 기법은 균등확률기법(EP:Equal probability)이다.
성능/효과
그리고 광고 메시지 전송의 결과, 즉 송신시도, 수신성공, 수신실패, 그리고 채널이 사용되지 않은 상황에 따라 적응적으로 전송 확률을 조정한다. 그러므로 본 기법에서는 네트워크의 기기 수를 알지 못해도 시간이 흐름에 따라 최적의 전송 확률로 수렴해 가며, 이웃 탐색에 소요되는 시간을 줄일 수 있다. 더불어 임의의 기기가 광고 메시지를 전송한 경우, 그 메시지가 성공적으로 전송되었는지 여부를 알 수 있는 충돌 감지 기법 (CD: Collision detection) [10], [11], [12]을 도입함으로써 확률적 이웃 탐색 기법의 성능을 더 높일 수 있다.
또한 모든 기기가 각자의 전송 범위 내에 존재하지 않는 멀티홉 환경에서도 PND 기법을 통해 이웃 탐색을 시행할 수 있다. 시뮬레이션을 통해 기존의 ALOHA-like neighbor discovery (AND) 기법[2]과 성능 비교를 수행하였으며 그 결과 이웃 탐지 과정에 소요되는 시간이 15.6% 감소함을 확인하였다. 또한 충돌 감지 기능을 적용했을 경우 최대 57.
6% 감소함을 확인하였다. 또한 충돌 감지 기능을 적용했을 경우 최대 57.0% 까지 이웃 탐지 시간을 줄일 수 있음을 확인하였다.
일반적으로, 메시지를 송신한 기기는 해당 시간 슬롯에서 충돌이 발생했는지 여부를 알 수 없으나, 물리 계층 정보를 통하거나 또 다른 라디오 채널을 통한 기법을 통해 충돌을 감지할 수도 있다[8]. 이러한 충돌 감지 기법을 통해 이웃 탐색에 소요되는 시간을 줄일 수 있고, 본 논문에서는 PND 기법에 충돌 감지 기법을 적용했을 때와 적용하지 않았을 때 모두 고려하였다. 네트워크에 존재하는 기기들은 고정된 위치를 지니고 있으며 각자 고유한 ID를 가지고 있다고 가정한다.
그림 3(b)에서 역시 점점 증가하는 최적값을 향해 수렴해 가는 전송 확률을 관찰할 수 있다. 본 결과를 통해 PND 기법이 최초의 확률을 무작위로 부여하더라도 시간 슬롯이 경과함에 따라 효과적으로 최적값에 수렴하는 것을 볼 수 있고, 결과적으로 네트워크에 존재하는 기기의 수를 알지 못하고, 최초의 전송 확률을 무작위로 부여하더라도 최적 전송 확률값에 수렴하는 것을 볼 수 있다.
PND(X,Y)는, X는 ccoll, Y는 cidle을 의미한다. PND(1.5, 1.5)는 AND 기법 대비 네트워크의 기기 수가 10개와 40개일 때 각각 3.1%와 15.6%의 소요시간 감소를 보였다. PND(1.
6%의 소요시간 감소를 보였다. PND(1.5, 1.5)는 또한 EP 기법 대비 기기 수가 40개일 때 9.1%만의 성능 하락을 보였다.
그림 5에서는 충돌 감지 기법이 적용된 경우의 소요 시간을 나타낸다. PND(1.5, 1.5)는 AND 기법 대비 기기 수가 10개와 40개일 때 각각 45.7%와 57.0%의 소요 시간 감소를 보였는데, 충돌 방지 기법을 PND 기법에 적용했을 때, 적용하지 않는 PND 기법 대비 기기 수가 10개와 40개일 때 각각 69.3%와 76.5%의 성능 향상을 보이는 것으로 보아 충돌 방지 기능이 PND 기법의 성능 향상에 큰 영향을 끼치는 것을 알 수 있다.
Linear 구조에서는 EP 기법, 즉 기기 개수의 역수의 값으로 광고 메시지를 전송하는 기법보다도 탐색 시간이 40.3% 감소되었음을 알 수 있는데, 모든 노드가 일렬로 나열된 환경이라면 실질적으로는 자신과 양 옆에 존재하는 기기 둘을 포함하여 1/3의 확률로 광고메시지를 전송하는 것이 최적값이나 EP 기법에서는 1/N, 즉 0.1의 확률로 광고메시지를 전송하게 되었다. 반면에 PND 기법을 사용하면 광고 메시지 전달 결과에 따라 분산적이고 자율적으로 전송 확률을 조정하기 때문에 최종 소요 시간이 감소하게 된다.
MIMD 정책을 통해 최적의 광고 메시지 전송 확률로 빠르게 접근함으로써 최적 소요시간에 근접한 성능을 보여준다. 비교 기법 대비 15.6~57%의 성능 향상을 볼 수 있었다. 더불어 충돌 감지 기능을 적용하면 적용하지 않았을 때 대비 70%의 소요 시간 감소 효과를 보임을 보였다.
6~57%의 성능 향상을 볼 수 있었다. 더불어 충돌 감지 기능을 적용하면 적용하지 않았을 때 대비 70%의 소요 시간 감소 효과를 보임을 보였다. 또한 하드웨어적인 추가나 수정 없이도 멀티홉 환경과 같은 다양한 환경에 사용될 수 있음을 보였다.
변수 ccoll과 cidle의 값은 본 PND 기법의 성능에 큰 영향을 주는 것을 알 수 있었다. 본 논문에서는 최적의 변수 값에 대한 고려는 하지 않았으나, 향후 최적의 변수 값을 도출해낼 수 있는 연구를 수행하여 보다 정밀한 기법을 제안할 수 있도록 할 예정이다.
후속연구
더불어 충돌 감지 기능을 적용하면 적용하지 않았을 때 대비 70%의 소요 시간 감소 효과를 보임을 보였다. 또한 하드웨어적인 추가나 수정 없이도 멀티홉 환경과 같은 다양한 환경에 사용될 수 있음을 보였다.
의 값은 본 PND 기법의 성능에 큰 영향을 주는 것을 알 수 있었다. 본 논문에서는 최적의 변수 값에 대한 고려는 하지 않았으나, 향후 최적의 변수 값을 도출해낼 수 있는 연구를 수행하여 보다 정밀한 기법을 제안할 수 있도록 할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
가장 기본적인 이웃 탐색 방법으로는 어떤 기법이 널리 사용되는가?
가장 기본적인 이웃 탐색 방법으로는, 매체 제어 프로토콜로 잘 알려진 ALOHA 기법이 널리 사용된다. 정해진 확률 p로 광고 메시지를 전송하고 그렇지 않으면 주위의 다른 광고 메시지를 수신할 수 있도록 광고 메시지 송신을 시도하지 않는 것이다.
PND 기법이 적용된 기기는 이웃 탐색 과정에 지속적으로 참여해야 하는 이유는 무엇인가?
PND 기법에서는 어떤 기기가 광고 메시지를 전송 하게 되는 경우 그 전송이 성공적으로 송신되었는지 여부를 알 수 있는 방법이 없다. 그렇기 때문에 그 기기가 성공적으로 광고 메시지를 전송하였다고 하더라도 기기는 지속적으로 이웃 탐색 과정에 참여할 수 밖에 없다.
PND 기법은 어떤 환경에서 동작되는가?
PND 기법은 분산적인 환경에서 동작된다. 즉, 모든 기기들은 각자의 전송 확률을 분산적으로 연산하여 그에 따라 광고 메시지를 slotted-ALOHA 프로토콜을 통해 브로드캐스팅한다.
참고문헌 (12)
L. G. Roberts, "ALOHA packet system with and without slots and capture, " ACM SIGCOMM Comput. Commun. Rev., vol. 5, no. 2, pp. 28-42, Apr. 1975.
S. Vasudevan, D. Towsley, D. Goeckel, and R. Khalili. "Neighbor discovery in wireless networks and the coupon collector's Problem, " in Proc. Mobicom, pp. 181-192, Beijing, China, Sept. 2009.
X. An, R. V. Prasad, and I. Niemegeers, "Neighbor discovery in 60 GHz wireless personal area networks, " in Proc. IEEE WoWMoM, pp. 1-8, Montreal, Canada, Jun. 2010.
L. You, Z. Yuan, P. Yang, and G. Chen, "ALOHA-like neighbor discovery for low-duty-cycled wireless sensor networks, " in IEEE WCNC, pp. 749-754, Cancun, Mexico, Mar. 2011.
H. Park, Y. Kim, and C.-H. Kang, "Cooperative neighbor discovery in 60GHz ad-hoc networks using directional antennas, " in Proc. KICS ICC, pp. 1165-1166. Jeju Island, Korea, Jun. 2011.
W. Kim and D. Cho, "Directional antenna based neighbor discovery for connectivity of wireless networks, " in Proc. KICS ICC, pp. 1412-1413, Jun. 2010.
J. H. Song, K. Kang, and Y.-J. Cho, "Fast neighbor discovery for construction of WPAN in extreme mobile network, " in Proc. KICS ICC, pp. 720-723, Nov. 2007.
M. Kim and W. Lee, "Analysis of neighbor discovery process with directional antenna for IEEE 802.15.3c, " J. KICS, vol. 37, no. 1, pp. 9-14, Jan. 2012.
S. Vasudevan, M. Adler, D. Goeckel, and D. Towsley, "Efficient algorithms for neighbor discovery in wireless networks, " IEEE/ACM Trans. Networking, vol. 21, no. 1, pp. 69-83, Feb. 2013.
F. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part II. the hidden terminal problem in carrier sense multiple-access and the busy-tone solution, " IEEE Trans. Commun., vol. 23, no. 12, pp. 1417-1433, Dec. 1975.
J. Peng, L. Cheng, and B. Sikdar, "A wireless MAC protocol with collision detection, " IEEE Trans. Mobile Computing, vol. 6, no. 12, pp. 1357-1369, Dec. 2007.
S. Sen, R. Roy Choudhury, and S. Nelakuditi, "CSMA/CN: Carrier sense multiple access with collision notification, " IEEE/ACM Trans. Networking, vol. 20, no. 2, pp. 544-556, Apr. 2012.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.