무선 센서 네트워크의 데이터 전송 특성을 고려한 효율적인 플러딩 기법 Efficient Flooding Mechanisms with Considering Data Transmission Characteristics of the Wireless Sensor Network원문보기
무선 센서 네트워크에서는 질의 분배(dissemination)나 이벤트 광고를 위해 플러딩이 요구된다. Simple(또는 blind) 플러딩은 폭주(implosion) 문제와 겹침(overlap) 문제를 야기하며, 따라서 simple 플러딩은 센서 네트워크의 수명을 감소시킬 수 있다. 따라서 본 논문에서는 플러딩 오버헤드를 줄이기 위해 플러딩 오버레이 구조(Flooding Overlay Structure; FOS)를 제안한다. 두 종류의 FOS 기법인 중앙형 FOS(Centralized FOS; CFOS)와 분산형 FOS(Distributed FOS; DFOS)를 제안하며, CFOS에서는 싱크가 네트워크 토폴로지 정보를 수집해서 그 정보를 기반으로 포워딩 노드를 선택하는 반면, DFOS에서는 각 센서 노드가 자신의 로컬 정보를 기반으로 자신이 브로드캐스트 패킷의 포워딩에 참여할지 여부를 결정한다. 제안한 FOS 기법들의 성능 분석을 위해 NS-2 기반의 시뮬레이션을 수행했으며, FOS 기법들과 simple 플러딩 및 gossiping의 성능을 비교했다. 시뮬레이션 결과, 제안한 FOS 기법들이 네트워크 수명 측면에서 simple 플러딩보다, 데이터 전달율 측면에서 gossiping보다 우수함을 알 수 있었다.
무선 센서 네트워크에서는 질의 분배(dissemination)나 이벤트 광고를 위해 플러딩이 요구된다. Simple(또는 blind) 플러딩은 폭주(implosion) 문제와 겹침(overlap) 문제를 야기하며, 따라서 simple 플러딩은 센서 네트워크의 수명을 감소시킬 수 있다. 따라서 본 논문에서는 플러딩 오버헤드를 줄이기 위해 플러딩 오버레이 구조(Flooding Overlay Structure; FOS)를 제안한다. 두 종류의 FOS 기법인 중앙형 FOS(Centralized FOS; CFOS)와 분산형 FOS(Distributed FOS; DFOS)를 제안하며, CFOS에서는 싱크가 네트워크 토폴로지 정보를 수집해서 그 정보를 기반으로 포워딩 노드를 선택하는 반면, DFOS에서는 각 센서 노드가 자신의 로컬 정보를 기반으로 자신이 브로드캐스트 패킷의 포워딩에 참여할지 여부를 결정한다. 제안한 FOS 기법들의 성능 분석을 위해 NS-2 기반의 시뮬레이션을 수행했으며, FOS 기법들과 simple 플러딩 및 gossiping의 성능을 비교했다. 시뮬레이션 결과, 제안한 FOS 기법들이 네트워크 수명 측면에서 simple 플러딩보다, 데이터 전달율 측면에서 gossiping보다 우수함을 알 수 있었다.
In the wireless sensor network, flooding is required for the dissemination of queries and event announcements. The simple flooding causes the implosion and the overlap problems, so the simple flooding may result in the reduced network lifetime. Therefore, in this paper, we propose the flooding overl...
In the wireless sensor network, flooding is required for the dissemination of queries and event announcements. The simple flooding causes the implosion and the overlap problems, so the simple flooding may result in the reduced network lifetime. Therefore, in this paper, we propose the flooding overlay structure (FOS) so that the overhead caused by flooding can be reduced. We propose two variants of FOS mechanisms, the centralized FOS (CFOS) and the distributed FOS (DFOS). In CFOS, the sink collects the network topology information and selects forwarding nodes based on that information. On the other hand, DFOS allows each sensor node to decide whether to act as a forwarding node or not based on its local information. For the performance evaluation of our proposed mechanisms, we carry out NS-2 based simulations and compare ours with the simple flooding and the gossiping. The simulation results indicate that the proposed FOS mechanisms outperform the simple flooding in terms of the network lifetime and the gossiping in terms of the data delivery ratio.
In the wireless sensor network, flooding is required for the dissemination of queries and event announcements. The simple flooding causes the implosion and the overlap problems, so the simple flooding may result in the reduced network lifetime. Therefore, in this paper, we propose the flooding overlay structure (FOS) so that the overhead caused by flooding can be reduced. We propose two variants of FOS mechanisms, the centralized FOS (CFOS) and the distributed FOS (DFOS). In CFOS, the sink collects the network topology information and selects forwarding nodes based on that information. On the other hand, DFOS allows each sensor node to decide whether to act as a forwarding node or not based on its local information. For the performance evaluation of our proposed mechanisms, we carry out NS-2 based simulations and compare ours with the simple flooding and the gossiping. The simulation results indicate that the proposed FOS mechanisms outperform the simple flooding in terms of the network lifetime and the gossiping in terms of the data delivery ratio.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
TTDD는 플러딩 오버헤드를 줄이기 위해서 그리드 구조를 사용하지만 모든 센서 노드가 자신의 위치를 알고 있다고 가정한다. 따라서 본 논문에서는 센서 노드가 자신의 위치를 알지 못 하는 환경에서 플러딩 오버헤드를 줄이면서도 데이터 전달을 보장해주는 방식을 제안하며, 이를 위해 플러딩 오버레이 구조(Flooding Overlay Structure; FOS)를 제안한다. 기존에, MANET 환경을 위한 효율적인 플러딩 기법들이 제안되었으며,[8][9][10]에 이들 기존 연구에 대한 정리가 되어 있다.
가장 단순한 브로드캐스트 기법으로 simple 플러딩이 있으나, simple 플러딩은 폭주와 겹침 문제를 야기해서 자원이 제약된 무선 센서 네트워크의 수명을 감소시킬 수 있다. 따라서 본 논문에서는 플러딩으로 인한 오버헤드를 감소시키기 위해서 오버레이 네트워크 개념을 도입한 플러딩 오버레이 구조(Flooding Overlay Structure; FOS)를 제안했으며, 두 종류의 FOS 기법인 CFOS(Centralized FOS)와 DFOS(Distributed FOS) 기법을 제안했다. CFOS에서는 싱크가 중앙집중형으로 효율적으로 FOS 노드를 결정하기 때문에 정적인 무선 센서 네트워크 환경에 보다 적합하다.
따라서, 본 논문에서는 단일의 고정 싱크를 갖는 센서 네트워크에서 빈번하게 플러딩을 하는 것으로 인한 오버헤드를 감소시키기 위해 브로드캐스트 데이터의 포워딩을 전담하는 센서 노드들로 구성된 플러딩 오버레이 구조(Flooding Overlay Structure; FOS)를 제안한다. 중앙형 FOS(Centralized FOS; CFOS)와 분산형 FOS(Distributed FOS)의 두 종류를 제안하며, 시뮬레이션을 통해 이들 기법의 성능을 분석한다.
가설 설정
Pulse 프로토콜은 주기적인 플러딩을 기반으로 동작하기 때문에 플러딩 관련 제어 메시지 오버헤드가 큰 문제가 있다. TTDD는 플러딩 오버헤드를 줄이기 위해서 그리드 구조를 사용하지만 모든 센서 노드가 자신의 위치를 알고 있다고 가정한다. 따라서 본 논문에서는 센서 노드가 자신의 위치를 알지 못 하는 환경에서 플러딩 오버헤드를 줄이면서도 데이터 전달을 보장해주는 방식을 제안하며, 이를 위해 플러딩 오버레이 구조(Flooding Overlay Structure; FOS)를 제안한다.
이 알고리즘에서 변수 Nbri는 센서 노드 i의 전송 반경 내에 있는 이웃 노드들과 센서 노드 i를 포함하는 노드들의 집합이며, Node_densityavg는 센서 네트워크의 평균 노드 밀도로 센서 네트워크에 살포되는 센서 노드 수와 센서 노드가 살포되는 영역의 면적을 기반으로 계산되어 각 센서 노드에 미리 설정되어 있다고 가정한다. δ는 threshold의 증감 값을 의미하며, 이웃 노드 수가 평균 노드 밀도보다 작으면(L3) threshold를 δ 만큼 감소시키고(L4) 그렇지 않으면(L5) δ만큼 증가시킨다(L6).
제안 방법
1. 네트워크 초기화 시에, 싱크는 전체 네트워크에 TD(Topology Discovery) 메시지를 브로드캐스팅함으로써 각 센서 노드에게 토폴로지 정보를 요청한다.
자세한 시뮬레이션 환경은 <표 1>과 같다. 2절의 관련 연구에서 언급한 rumor 라우팅과 SPIN은 FOS 기법과는 다른 데이터 교환 패턴을 갖고 있고, pulse 프로토콜의 성능은 simple 플러딩 주기 값에 의존적이며, TTDD는 센서 노드들이 위치 정보를 알 수 있어야만 하기 때문에, 본 성능 분석에서는 FOS 기법들을 simple 플러딩 및 gossiping과만 비교했다.
단일의 고정 싱크를 갖는 센서 네트워크에서의 빈번한 플러딩으로 인한 오버헤드를 줄이기 위해 일부 센서 노드들만 브로드캐스트 메시지의 전달에 참여하도록 하는 중앙형 FOS(Centlralized FOS; CFOS)와 분산형 FOS(Distributed FOS; DFOS)를 제안한다. FOS 방식은 일부 노드만 브로드 캐스트 메시지의 전달에 참여하게 함으로써 포워딩에 참여하지 않는 노드들의 전력 소모를 줄여서 에너지 효율적인 플러딩이 가능하도록 한다.
2장에서 언급한 기존의 다른 효율적인 플러딩 방법들의 경우 메시지를 브로드캐스트할 때 마다 매번 포워딩에 참여할지 여부를 각 센서 노드가 결정하며 이로 인해 센서 노드의 컴퓨팅 파워가 소모되게 된다. 본 논문에서 제안하는 방식에서는 네트워크 초기 설정 시에 FOS 노드가 일단 결정되면 그 이후에는 FOS 노드만 브로드캐스트 메시지 포워딩에 참여하고 FOS 노드가 아닌 센서 노드는 브로드캐스트 메시지 포워딩에 참여하지 않기 때문에 브로드캐스트 메시지 포워딩 여부를 매 브로드캐스트 메시지마다 결정하지 않아도 되기 때문에 센서 노드의 전력소모를 줄일 수 있게 된다.
10-4J 보다 작은 가용 노드 에너지는 노드가 더 이상 동작할 수 없음을 뜻하도록 했다. 이벤트는 2초마다 센서 네트워크의 임의의 지역에서 uniform하게 발생하게 했으며, 싱크는 1초마다 질의를 생성하게 했다. 자세한 시뮬레이션 환경은 <표 1>과 같다.
일반적인 센서 네트워크의 밀도(즉, 어떤 노드의 평균 이웃 노드 수 αi)는 6~12[14] 이기 때문에 αmax는 12보다 큰 값인 16으로 설정했으며, αi가 6~12일 때 δi가 2~3 사이 값을 갖도록 하는 k = 3을 향후 성능 분석을 하는데 사용한다.
따라서, 본 논문에서는 단일의 고정 싱크를 갖는 센서 네트워크에서 빈번하게 플러딩을 하는 것으로 인한 오버헤드를 감소시키기 위해 브로드캐스트 데이터의 포워딩을 전담하는 센서 노드들로 구성된 플러딩 오버레이 구조(Flooding Overlay Structure; FOS)를 제안한다. 중앙형 FOS(Centralized FOS; CFOS)와 분산형 FOS(Distributed FOS)의 두 종류를 제안하며, 시뮬레이션을 통해 이들 기법의 성능을 분석한다.
대상 데이터
시뮬레이션은 1000m × 1000m 영역에 100개의 센서 노드들이 랜덤하게 분포된 센서 네트워크에 대해서 수행했다.
제안한 FOS 기법의 성능을 분석하기 위해서 NRL 센서 네트워크 확장 패키지[12]를 포함하는 NS-2 시뮬레이터[13]를 사용해서 시뮬레이션을 수행했다. 시뮬레이션은 1000m × 1000m 영역에 100개의 센서 노드들이 랜덤하게 분포된 센서 네트워크에 대해서 수행했다.
데이터처리
반면, DFOS에서는 각 센서 노드가 자체적으로 브로드캐스트 메시지의 포워딩에 참여할지 여부를 결정한다. 제안된 FOS 방법들의 성능 분석을 위해 NS-2 시뮬레이터를 사용해서 simple 플러딩 및 gossiping과의 성능 비교를 수행했다. 시뮬레이션 결과, FOS 방법들이 simple 플러딩 방법에 비해서 네트워크 수명 측면에서 우월함을 알 수 있었으며, 데이터 전달율 측면에서는 FOS 방법들이 simple 플러딩과 성능이 거의 비슷하거나 gossiping보다 훨씬 우수함을 알 수 있었다.
성능/효과
3. DFOS에서 네트워크 연결성을 제공하는 것은 CFOS에서 보다 더 어려우며, 네트워크 연결성을 제공하기 위해서 notice delay 개념을 도입한다. 각 FOS 후보 노드는 이웃 노드들의 수를 기반으로 notice delay를 결정한다.
4. FOS 후보 노드가 아닌 센서 노드는 μτ 동안 이웃 노드들로부터 Notice 메시지를 하나도 수신하지 못 하면 FOS 노드가 되며, 1-홉 플러딩으로 Notice 메시지를 보냄으로써 이웃 노드들에게 자신이 FOS 노드가 되었음을 알린다.
5. FOS 패킷을 수신한 센서 노드는 자신이 FOS 노드인지 여부를 알 수 있으며, 만일 FOS 노드이면 브로드캐스트 패킷의 포워딩에 참여한다. FOS 노드들은 브로드캐스트 패킷을 포워딩하게 함으로써 simple 플러딩의 폭주 문제를 완화시킨다.
6. FOS 노드의 에너지가 일정 수준 이하로 떨어지면 이웃 노드들에게 RD(Ready-to-Die) 패킷을 1-홉 플러딩으로 전송함으로써 자신의 에너지가 고갈되었음을 알린다. RD 메시지를 수신한 이웃 노드들은 자신의 상태를 FOS 노드로 설정하고 브로드캐스트 패킷의 플러딩에 참여한다.
DFOS의 포워딩 노드 수는 3, 4개의 포워딩 노드를 갖는 gossiping의 포워딩 노드 수와 비슷하다. DFOS가 gossiping 보다 적은 수의 포워딩 노드들로 훨씬 높은 데이터 전송율을 보임을 알 수 있고, 그 이유는 DFOS가 gossiping보다 효율적으로 포워딩 노드를 선택함을 뜻한다. Simple 플러딩 이외의 다른 기법들에서는 노드 밀도가 증가함에 따라 포워딩 노드 수가 감소하며, 따라서 네트워크 수명이 증가하게 된다.
제안된 FOS 방법들의 성능 분석을 위해 NS-2 시뮬레이터를 사용해서 simple 플러딩 및 gossiping과의 성능 비교를 수행했다. 시뮬레이션 결과, FOS 방법들이 simple 플러딩 방법에 비해서 네트워크 수명 측면에서 우월함을 알 수 있었으며, 데이터 전달율 측면에서는 FOS 방법들이 simple 플러딩과 성능이 거의 비슷하거나 gossiping보다 훨씬 우수함을 알 수 있었다.
(그림 5)는 노드 밀도의 변화에 따른 데이터 전달율을 보여준다. 시뮬레이션 결과에 의하면 CFOS는 simple 플러딩과 거의 비슷한 성능을 보이며, DFOS는 85% 정도의 데이터를 성공적으로 전달한다. Gossiping은 노드 밀도가 커지면 데이터 전달율도 증가하지만, 기본적으로 데이터 전달율이 1/2 또는 1/3 수준으로 매우 낮기 때문에 simple 플러딩을 대체하기에는 역부족이다.
질의응답
핵심어
질문
논문에서 추출한 답변
센서 노드의 특징은 무엇인가?
무선 센서 네트워크는 이동 애드혹 네트워크(Mobile Ad Hoc Network; MANET)와 여러 면에서 차이가 있다. 센서 노드는 MANET 노드에 비해서 이동성이 거의 없거나 정적이며 에너지가 훨씬 제약되어 있고, 센서 네트워크의 노드 밀도가 MANET의 노드 밀도보다 일반적으로 높다는 특징이 있다. 센서 네트워크의 가장 중요한 이슈 중의 하나는 네트워크 수명(lifetime)을 연장시키는 것으로, 일반적으로 네트워크 수명은 센서 노드가 처음으로 에너지 고갈로 인해 동작을 멈추는 시점까지로 정의된다.
본 연구에서 제안한 플러딩 오버레이 구조의 두 종류는 무엇인가?
따라서, 본 논문에서는 단일의 고정 싱크를 갖는 센서 네트워크에서 빈번하게 플러딩을 하는 것으로 인한 오버헤드를 감소시키기 위해 브로드캐스트 데이터의 포워딩을 전담하는 센서 노드들로 구성된 플러딩 오버레이 구조(Flooding Overlay Structure; FOS)를 제안한다. 중앙형 FOS(Centralized FOS; CFOS)와 분산형 FOS(Distributed FOS)의 두 종류를 제안하며, 시뮬레이션을 통해 이들 기법의 성능을 분석한다.
Simple(또는 blind) 플러딩의 단점은 무엇인가?
무선 센서 네트워크에서는 질의 분배(dissemination)나 이벤트 광고를 위해 플러딩이 요구된다. Simple(또는 blind) 플러딩은 폭주(implosion) 문제와 겹침(overlap) 문제를 야기하며, 따라서 simple 플러딩은 센서 네트워크의 수명을 감소시킬 수 있다. 따라서 본 논문에서는 플러딩 오버헤드를 줄이기 위해 플러딩 오버레이 구조(Flooding Overlay Structure; FOS)를 제안한다.
참고문헌 (14)
G. J. Pottie and W. J. Kaiser, 'Wireless Integrated Network Sensors,' Communications of the ACM, Vol.43, No.5, pp. 51-58, May, 2000
C. Intanagonwiwat, R. Govindan and D. Estrin, 'Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks,' ACM Mobicom, pp.56-67, Aug., 2000
D. Braginsky and D. Estrin, 'Rumor Routing Algorithm for Sensor Networks,' ACM WSNA, pp.22-31, Sept., 2002
B. Awerbuch, D. Holmer, H. Rubens, K. Chang and I.-J. Wang, 'The Pulse Protocol: Sensor Network Routing and Power Saving,' IEEE Milcom, pp.662-667, Nov., 2004
J. Kulik, W. Heinzelman and H. Balakrishnan, 'Negotiationbased Protocols for Disseminating Information in Wireless Sensor Networks,' Wireless Networks, Vol.8, pp.169-185, 2002
M.-J. Lin, K. Marzillo and S. Masini, 'Gossip versus Deterministic Flooding: Low Message Overhead and High Reliability for Broadcasting on Small Networks,' DISC, pp. 253-267, 2000
F. Ye, H. Luo, J. Cheng, S. Lu and L. Zhang, 'A Two-Tier Data Dissemination Model for Large-scale Wireless Sensor Networks,' ACM Mobicom, pp.148-159, Sept., 2002
F. Ingelrest, D. Simplot-Ryl and I. Stojmenovic, 'Energy Efficient Broadcasting in Wireless Mobile Ad Hoc Networks,' Resource Management in Wireless Networking, Kluwer Academic Publishers, 2004
W. Lou and J. Wu, 'Toward Broadcast Reliability in Mobile Ad Hoc Networks with Double Coverage,' IEEE Transactions on Mobile Computing, Vol.6, No.2, pp.148-163, Feb., 2007
※ AI-Helper는 부적절한 답변을 할 수 있습니다.