Directed Diffusion for Wireless Sensor Networking C. Intanagonwiwat, R. Govindan, D. Estrin, John Heidemann, and Fabio Silva ACM/IEEE 2003 안녕하세요. Directed Diffusion for Wireless Sensor Networking에 대해 발표 할 컴퓨터 공학과 김영삼 입니다. Directed Diffusion에 대해 간략히 설명드리겠습니다. Directed Diffusion은 무선 센서 네트워크를 위한 대표적인 데이터 중심적 라우팅 기법입니다. 속성 기반 네이밍 스킴을 사용하고, 필터링이라고 하는 네트워크 내부에서의(in-network) 프로세싱을 지원합니다. 데이터는 속성과 값의 쌍으로 표현하고 있습니다. Young-sam Kim / M.D Course School of Information Technology Dept. of Computer Engineering Korea University of Technology and Education

Contents Introduction Directed Diffusion Simplified schematic for Directed Diffusion Data Naming Interest & Gradient Interest Propagation Data Propagation Reinforcement Simulations Conclusion 발표는 연구동향 및 용어 설명을 하는 Introduction, 본 논문에서 제안하는 기법인 Directed Diffusion 그리고 실험 및 결과를 보여주는 Simulations 마지막으로 결론인 Conclustion 순으로 발표 하도록 하겠습니다. 2008-06-03

- Introduction - 첫번째로 Introduction 입니다. 2008-06-03

Introduction (1/2) Event A sensor field Directed Diffusion Wireless sensor networks Sensing devices with communication capability Event monitoring Enemy detection, aircraft interiors, large industrial plants Data-centric communication Data is named by attribute-value Different form IP-style communication End-to-end delivery service Sources Event Directed Diffusion Wireless sensor networks에 대해서는 다들 많이 아시기 때문에 넘어가도록 하겠습니다. 본 논문에서 제안하는 Directed Diffusion은 데이터 중심적인 라우팅 기법입니다. 여기서 데이터란 속성값이 되겠고, 기존의 Ip-style 통신에서 사용하는 주소 중심적인 어드레싱 과는 달리 해당 데이터를 가진 노드들에게 데이터를 요구하는 방식을 말합니다. Sink Node 2008-06-03

Introduction (2/2) Data-centric communication (cont.) Human operator’s query (task) is diffused Sensors begin collecting information about query Information returns along the reverse path Intermediate nodes aggregate the data Combine reports from sensors Challenges Scalability Energy efficiency Robustness / Fault tolerance in outdoor areas Efficient routing 예를 들면 휴먼 오퍼레이터가 “40`C 이상되는 온도를 센싱한 노드는 데이터를 보내라” 라고 query를 발생시키면 센서들은 Query에 대한 정보를 수집하기 시작합니다. 그리고 query 에 대한 정보를 가진 센서들은 query를 전달 받은 경로를 통해 반대로 싱크노드에게 데이터를 전송합니다. 그리고 중간 노드들은 다른 노드들로부터 받은 보고를 통합하여 데이터를 병합하게 됩니다. 이것이 데이터 중심적 통신 방식이 되겠습니다. 하지만 이러한 통신방식에도 불구하고 향후 개선하고 해결해야 할 문제점들이 남아있습니다.Challenges = 과제 확장성 문제 에너지 효율성 문제 실외에서 오류에 잘 견디고 보다 강력하게 해야 하는 문제 효율적인 라우팅 개선문제 2008-06-03

- Directed Diffusion - 다음으로 본 논문에서 제안하는 Directed Diffusion에 대해 말씀드리도록 하겠습니다. 2008-06-03

Simplified schematic for DD 우선 Directed Diffusion을 간략한 개념도를 통해 설명 드리도록 하겠습니다. 그림은 싱크 노드가 질의에 해당하는 Interest를 네트워크 전체에 플러딩하는 모습입니다. 이때 Interest를 받은 센서노드는 이웃 노드들에 대한 테이블을 유지하며, 패킷이 전달될 이웃 노드들에 대한 경사를 설정하게 됩니다. (b)그림은 해당하는 질의를 만족하는 데이터를 가진 노드가 소스 노드가 되어서 설정된 다중의 경사 방향으로 탐사 데이터 (exploratory data)를 전송하는 그림입니다. (c)그림은 데이터를 받은 싱크 노드가 불필요한 데이터 전송을 방지하기 위하여 특정한 경사를 강화하여 강화된 경로를 통하여 데이터를 전송하는 그림입니다. Directed Diffusion에 대해 좀더 자세히 설명드리도록 하겠습니다. 2008-06-03

Request: Interest(task) Data Naming Content based naming Task are named: Attribute – value pair Selecting naming scheme important No globally unique ID for nodes: only locally unique Request: Interest(task) type = four-legged animal interval = 20 ms duration = 10 seconds rect = [-100,100,200,400] Reply: Data type = four-legged animal instance = elephant location = [125, 220] intensity = 0.6 confidence = 0.85 timestamp = 01:20:40 첫번째로 Directed Diffusion은 속성 기반 네이밍 스킴(체계)을 사용합니다. 그리고 데이터는 속성과 값의 쌍으로 표현되며. 네이밍에 관해 쉽게 설명하기 위해 본 논문에서는 Rectangle 이라는 소지역에서 GPS 협력 시스템 기반으로 동물을 추적 하는 것을 예로 들고 있습니다. 왼쪽값은 task를 요청하는 Interest 메시지에 들어있는 데이터 값들입니다. 오른쪽의 값들은 이러한 task에 응답하는 동물을 감지한 센서가 생성한 데이터를 예로 속성과 값들로 표현되어 있는 것을 보여주고 있습니다. 본 논문의 목적은 확산개념에 대한 이해를 얻는것이기 때문에 네이밍 스킴에 관한 자세한 연구는 뒤로 미루어 졌습니다. 2008-06-03

Interest & Gradient Interest describes a task needed to be done by the sensor network Interests are injected into the network at sink. Sink broadcasts the interest. Interval specifies an event data rate. Interest is periodically refreshed by the sink. Every Node maintains an interest cache. Interest entry contains several gradient fields. Specifies a data rate and a direction (neighbor) Data flows from the source to the sink along the gradient 다음으로 본 논문에서 사용하는 Interest와 Gradient에 대해 설명 드리겠습니다. Interest는 sensor network에 의해 완료되어질 필요가 있는 작업을 말합니다. 그리고 다음과 같은 특성이 있습니다. - Interest는 싱크노드를 통해 전체 네트워크에 주입. - 이때 브로드 캐스트 방식을 사용. - Interval은 이벤트 데이터 발생율을 명확히 함. - 초기에 Interval은 필요 수 이상으로 요청함. - 노드는 Iinterest cache를 유지함. 그리고 본 논문에서는 Initial Intereset 네이밍 스킴을 보여주고 있는데 초기에는 탐사 메시지를 띄워야 하기 때문에 Interval을 느리게 설정하여 전송한다는 것 이외에는 별다른 것이 없어 뺐습니다. 다음으로 Interest entry는 여러 개의 경사 필드를 포함하고 있습니다. 이런 Gradient fields의 특성으로는 Data rate와 방향을 명확히 하는 것입니다. 이것은 각각의 경사가 data rate 필드와 duration 필드를 가지고 있기 때문에 data rate를 명확히 할 수 있고(interval of interest), duration 필드를 통해 interest의 lifetime을 어림잡아 계산할 수도 있는 것입니다.(timestamp, expiresAt). 그리고 경사라는 개념을 통해 소스로부터 싱크까지 데이터가 흐를 수 있게 합니다. 2008-06-03

Interest Propagation Source Sink Flooding Constrained or Directional flooding based on location. Directional Propagation based on previously cached data. Gradient Source Interest 방금 전까지 설명 드린 Interest의 전송에 관련하여 설명드리도록 하겠습니다. 본 논문에서는 타켓 인식 알고리즘은 자세하게 다루고 있지 않았습니다. Interest는 브로드캐스트 방식으로 Flooding 됩니다. 그리고 강제적 혹은 직접적인 위치기반의 Flooding과정을 가집니다. 그리고 이전의 캐쉬 데이터기반으로 직접적인 전달 과정을 가집니다. 그럼 그림을 통해 자세히 설명하도록 하겠습니다. Sink 2008-06-03

Data Propagation Source Sink Reinforcement to single path delivery. Multipath delivery with probabilistic forwarding. Multipath delivery with selective quality along different paths. Gradient Source Data 하나의 경사로 데이터를 전달하기 위해 강화과정을 거친다. 첫째. 확률적 포워딩 방식으로 다중경로로 전송한다. 둘째. 다른 경로들 중 가장 질 높은 경로를 선택하여 전송한다. Sink 2008-06-03

Reinforcement Source Sink Reinforce one of the neighbor after receiving initial data. Neighbor(s) from whom new events received. Neighbor who’s consistently performing better than others. Neighbor from whom most events received. Gradient Source Data Reinforcement Sink 2008-06-03

Negative Reinforcement(1/2) Explicitly degrade the path by re-sending interest with lower data rate. Time out Gradient Source Data Reinforcement Sink 2008-06-03

Negative Reinforcement(2/2) Using negative reinforcement Path Truncation Loop removal For resource saving B negative reinforces D, D negative reinforces E, … 2008-06-03

- Simulation - 2008-06-03

Performance Evaluation (1/7) Simulator: ns-2 Network Size: 50-250 Nodes Transmission Range: 40m Constant Density: 1.95x10-3 nodes/m2 (9.8 nodes in radius) MAC: Modified Contention-based MAC Transceiver Energy Model: mimics a “sensor radio” 660 mW in transmission, 395 mW in reception, and 35 mW in idle Comparison with Flooding Omniscient multicast 2008-06-03

Performance Evaluation (2/7) Average dissipated energy 0.018 0.016 Flooding 0.014 0.012 0.01 Average Dissipated Energy (Joules/Node/Received Event) 0.008 Omniscient Multicast 0.006 Diffusion 0.004 Due to the data-aggregation Nodes suppress duplicate location estimates 0.002 50 100 150 200 250 300 Network Size 2008-06-03

Performance Evaluation (3/7) Average delay 0.35 0.3 Flooding 0.25 Average Delay (secs) 0.2 0.15 0.1 Omniscient Multicast Diffusion 0.05 Uncongested sensor network Reinforcement rules find the low delay path 50 100 150 200 250 300 Network Size 2008-06-03

Performance Evaluation (4/7) Impact of dynamics (Distinct event delivery ratio) 2008-06-03

Performance Evaluation (5/7) Impact of negative reinforcement Diffusion With Negative Reinforcement Diffusion Without Negative Reinforcement Prune off higher latency path 2008-06-03

Performance Evaluation (6/7) Impact of duplicate suppression Diffusion With Suppression Diffusion Without Suppression Negative reinforcement Suppress identical data sent 2008-06-03

Performance Evaluation (7/7) High idle radio power 2008-06-03

- Conclutsion - 2008-06-03

Conclusion Application-level data dissemination has the potential to improve energy efficiency significantly Data-centric dissemination Reinforcement based adaptation of paths Duplicate suppression and aggregation MAC for sensor networks needs to be designed carefully. 2008-06-03

- Q & A - 2008-06-03

- Thank you - 2008-06-03