대규모 센서 네트워크를 위한 최적-동기식 병렬 시뮬레이션 = Optimal-synchronous Parallel Simulation for Large-scale Sensor Network

국문 초록 (Abstract)

대규모 무선 센서 네트워크의 설계 및 응용 개발을 위하여 소프트웨어 시뮬레이션이 널리 사용되고 있다. 그러한 시뮬레이션에서 네트워크의 동작과 실행시간 및 전력소모량을 가능한 한 정확히 예측하기 위해서는 시뮬레이션 정밀도가 높아야 한다. 그러나 정밀도가 높아질수록 시뮬레이션 시간은 길어지며, 센서노드의 수가 증가하면 그 시간이 더욱 길어진다. 본 연구에서는 대규모 무선 센서 네트워크 시뮬레이션에 걸리는 시간을 단축하기 위한 최적-동기식 병렬 이산-사건 시뮬레이션 방법을 제안한다. 이 방법에서는 네트워크로 연결된 여러 대의 컴퓨터들이 작업부하인 센서노드들을 분할하여 시뮬레이션 한다. 제안한 방법으로 구현한 시뮬레이터를 이용하여 실험한 결과에 따르면, 시뮬레이션 되는 센서노드의 수가 많은 경우에는 병렬 시뮬레이션에 참여하는 컴퓨터 수의 제곱에 접근하는 속도향상을 얻을 수 있다는 것을 확인하였다. 이 경우에 시뮬레이션 되는 센서노드의 수가 많아질수록 전체 시뮬레이션 시간에서 차지하는 병렬 시뮬레이션 오버헤드의 비율은 무시할 수 있을 정도로 작아지기 때문에, 컴퓨터의 수가 충분하다면 시뮬레이션 할 수 있는 센서노드의 수에는 한계가 없게 된다. 또한 LAN에 연결된 PC들을 그대로 사용하기 때문에, 병렬 시뮬레이션 환경을 저렴한 비용으로 쉽게 구축할 수 있다는 장점이 있다.

다국어 초록 (Multilingual Abstract)

Software simulation has been widely used for the design and application development of a large-scale wireless sensor network. The degree of details of the simulation must be high to verify the behavior of the network and to estimate its execution time and power consumption of an application program as accurately as possible. But, as the degree of details becomes higher, the simulation time increases. Moreover, as the number of sensor nodes increases, the time tends to be extremely long. We propose an optimal-synchronous parallel discrete-event simulation method to shorten the time in a large-scale sensor network simulation. In this method, sensor nodes are partitioned into subsets, and each PC that is interconnected with others through a network is in charge of simulating one of the subsets. Results of experiments using the parallel simulator developed in this study show that, in the case of the large number of sensor nodes, the speedup tends to approach the square of the number of PCs participating in the simulation. In such a case, the ratio of the overhead due to parallel simulation to the total simulation time is so small that it can be ignored. Therefore, as long as PCs are available, the number of sensor nodes to be simulated is not limited. In addition, our parallel simulation environment can be constructed easily at the low cost because PCs interconnected through LAN are used without change.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 명령어-레벨의 센서 네트워크 시뮬레이션
• 3. 시뮬레이터의 내부 구조
• 4. 병렬 이산-사건 시뮬레이션
• 5. 실험
• 6. 결론
• 참고문헌

참고문헌 (Reference)

1 김방현, "전력소모량 및 실행시간 추정이 가능한 센서 네트워크 시뮬레이터의 개발" 한국시뮬레이션학회 15 (15): 35-42, 2006

2 The NEST Project, "http://webs.cs.berkeley.edu/"

3 D.A. Jeerson, "Virtual Time" 7 (7): 404-425, 1985

4 P. Levis, "TOSSIM: Accurate and Scalable Simulation of Entire TinyOS Applications" 2003

5 J. Hill, "System Architecture Directions for Networked Sensors" 2000

6 Chipcon, "SmartRF CC2420 Preliminary Datasheet 1.2" 2004

7 G. Simon, "Simulation-based Optimization of Communication Protocols for Large-scale Wireless Sensor Networks" 2003

8 M. H. MacDougall, "Simulating Computer Systems: Techniques and Tools" MIT Press 1987

9 A. Ledeczi, "Simple Nest Application Simulator" Draft, Institute for Software Integrated Systems 2001

10 J. Xu, "Predicting the Performance of Synchronous Discrete Event Simulation" 15 (15): 1130-1137, 2004

11 A. Ferscha, "Parallel and Distributed Simulation of Discrete Event Systems" McGraw-Hill 1995

12 CrossBow, "MPR/MIB Users Manual" 2005

13 J. Xu, "Efficiently Unifying Parallel Simulation Techniques" 2006

14 K.M. Chandy, "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs" SE-5 (SE-5): 440-452, 1979

15 J.K. Peacock, "Distributed Simulation using a Network of Processors" 3 (3): 44-56, 1979

16 J. Misra, "Distributed Discrete-Event Simulation" 18 (18): 39-65, 1986

17 B.L. Titzer, "Avrora: Scalable Sensor Network Simulation with Precise Timing" 2005

18 Atmel, "ATmega128(L) Complete" 2006

19 J. Polley, "ATEMU: A Fine-grained Sensor Network Simulator" 2004

20 R.E. Bryant, "A Switch-Level Model and Simulator for MOS Digital Systems" C-33 (C-33): 160-177, 1984