Transcript seminar
INFOCOM 2008. The 27th Conference on Computer Communications. IEEE AdapCode: Adaptive Network Coding for Code Updates in Wireless Sensor Networks I-Hong Hou, Yu-En Tsai, Tarek F. Abdelzaher, Indranil Gupta Department of Computer Science University of Illinois, Urbana, IL 61801 指導教授 : 陳 敬 博士 Reporter : 黎俊廷 100學年度第一學期專題研討 2011.11.24 Outline Introduction Adaptive Network Coding Simulation Conclusions References 2015/4/13 2 Introduction Wireless Sensor Network (WSN) Code Update Network Coding 2015/4/13 3 Introduction - WSN 2015/4/13 4 Introduction – Code Update WSN 由多個感測節點所組成，這些節點在被佈建前， 會先依據其應用而預載入一些code，之後，眾多的節 點才被佈建在目標區域。 但由於是不熟悉的環境，研究過程中常會依環境條件 改變及需求的不同發展出新的sensing functions，新的 functions 往往不在預載入的code中。 為了節省成本與時間，也不該大費周章的重新佈建新 的節點以滿足不同的需求，取而代之的方法即是 Code Update。(類似 patch的動作) 2015/4/13 5 Code Update vs. Sensing Data Dissemination 資料流方向不同、資料量大小不同、參與 的節點數可能差異甚多、可靠度的要求。 2015/4/13 6 Introduction – Network Coding a b 共6次 共4次 → Network Coding 2015/4/13 7 Adaptive Network Coding Protocol Overview There is one single source in the system. The source will keep sending packets containing those messages. To divide the messages into sequentially numbered pages. Each page contains a fixed number M of messages. 2015/4/13 8 Adaptive Network Coding Protocol Overview The source will keep on transmitting packets and will pause for a period of T milliseconds after finishing a page. The choice of T is a tradeoff between traffic and propagation time. 2015/4/13 9 Adaptive Network Coding Protocol Overview When it succeeds in decoding all messages within a page, it determines its coding scheme, N, according to the number of its neighbors. avgNeighbor 0~4 5~7 8~10 11~ N 1 2 4 8 After determining the coding scheme, the node sends out M/N packets. 2015/4/13 10 Adaptive Network Coding Protocol Overview n data messages ... t bits a page , M＝8 2015/4/13 11 Adaptive Network Coding Protocol Overview a page , M＝8 Node if N ＝4 經過線性組合 New packet : Page # Coefficient Vector data Note M : Global N : Local p : Global 2015/4/13 The coefficients (ai) of each linear combination are randomly chosen from 0 to p − 1 , 12 Adaptive Network Coding Protocol Overview Adaptively Determining Coding Scheme After the sensor succeeds in decoding that page, using the formula: avgNeighbor = α × avgNeighbor + (1 − α ) × curNeighbor. The value of α should be determined according to the stability of the network. 2015/4/13 13 Adaptive Network Coding Dealing with NACKs 就 "求救者" 而言 During the code update process, every node keeps a countdown timer. A node will send out a NACK to the local broadcast address when the timer fires. In the NACK packet, the sensor will indicate the page number it is asking for and messages it needs to decode all messages in the page. 但, 問題是……??? 2015/4/13 14 Adaptive Network Coding Dealing with NACKs 就 "救人者" 而言 看看自己有無 能夠幫上忙的地方 When a node receives a NACK message, it first checks whether it can reply with the needed data. 2015/4/13 若有，選擇觀望， 先不急著出手搭救， If it can do so, the node will delay for a random period of time to see if any of its neighbors is replying to this NACK. 若其他人都沒出 手搭救，則我救 If no reply is heard before the timeout, this node will respond to the NACK by sending all messages indicated in the NACK. 15 Adaptive Network Coding - Flow Chart (For a Node) if a packet is received construct coeffMatrix， 欲求 計算線性組合之解 若得到完整page ( 長度M ) Broadcast M/N packets If a NACK is received （此部份依照上頁所述之流程） If timeout, send a NACK 2015/4/13 16 Simulation Simulation Settings (1/2) To consider a 10 × 10 grid of MICAZ nodes simulated in TOSSIM of TinyOS version 2. To compare AdapCode with Deluge, the state-of-art code dissemination protocol. To assume that the source needs to broadcast a piece of code that can be divided into D packets. To run both protocols 50 times in a grid deployment for each grid size between 4 m and 7 m, that is, the total area sizes are between 40 m and 70 m. 2015/4/13 17 Simulation Simulation Settings (2/2) To evaluate the performance for both D = 128 and D = 1024 ,which approximately corresponds to code images with sizes 2KB and 20KB. Also evaluate the traffic and load balance under random deployments. The source will pause for T=300 milliseconds after transmitting a page. 2015/4/13 18 2015/4/13 19 Conclusions The core idea of AdapCode is to Using network coding to reduce data packets. Exploit adaptive behavior to choose the best coding scheme to reduce NACK/reply packets. 2015/4/13 20 References [1] Updating Software in Wireless Sensor Networks: A Survey S. Brown, Dept. of Computer Science, National University of Ireland, Maynooth C.J. Sreenan, Mobile & Internet Systems Laboratory, Dept. of Computer Science, University College Cork, Ireland [2] Wireless sensor networks: a survey I.F. Akyildiz, W. Su , Y. Sankarasubramaniam, E. Cayirci Broadband and Wireless Networking Laboratory, School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA [3] Efficient power savings in wireless sensor networks with network coding and overhearing avoidance Hnin Yu Shwe and Xiaohong Jiang Electrical and Communication Engineering, Graduate School of Engineering, Tohoku University, 6-6-05 Aza-Aoba,Aramaki, Aobaku, Sendai, 980-8579 Japan. 2015/4/13 21 Q&A 2015/4/13 22