博碩士論文查詢聯邦系統首頁 聯絡信箱 關於我們 加入我們

本論文已被瀏覽 46 次, [ 造訪詳細資料與全文 ] 31 次,[ 回到前頁查詢結果 ] [ 重新搜尋 ]

A (Truly) Local Broadcast Layer for Unreliable Radio Networks.

作者:Calvin Newport, Nancy Ann Lynch,
出版單位:Association for Computing Machinery (ACM)
核准日期:2016-01-15
類型:Article http //purl.org/eprint/type/ConferencePape
權限:Creative Commons Attribution-Noncommercial-Share Alike.http://creativecommons.org/licenses/by-nc-sa/4.0/....

英文摘要

In this paper, we implement an efficient local broadcast service for the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Our local broadcast service offers probabilistic latency guarantees for: (1) message delivery to all reliable neighbors (i.e., neighbors connected by reliable links), and (2) receiving some message when one or more reliable neighbors are broadcasting. This service significantly simplifies the design and analysis of algorithms for the otherwise challenging dual graph model. To this end, we also note that our solution can be interpreted as an implementation of the abstract MAC layer specification---therefore translating the growing corpus of algorithmic results studied on top of this layer to the dual graph model. At the core of our service is a seed agreement routine which enables nodes in the network to achieve "good enough" coordination to overcome the difficulties of unpredictable link behavior. Because this routine has potential application to other problems in this setting, we capture it with a formal specification---simplifying its reuse in other algorithms. Finally, we note that in a break from much work on distributed radio network algorithms, our problem definitions (including error bounds), implementation, and analysis do not depend on global network parameters such as the network size, a goal which required new analysis techniques. We argue that breaking the dependence of these algorithms on global parameters makes more sense and aligns better with the rise of ubiquitous computing, where devices will be increasingly working locally in an otherwise massive network. Our push for locality, in other words, is a contribution independent of the specific radio network model and problem studied here.

Ford Motor Company. University Research Program

National Science Foundation (U.S.) (Award CCF-1320279)

National Science Foundation (U.S.) (Award CCF-0937274)

National Science Foundation (U.S.) (Award CCF-1217506)

National Science Foundation (U.S.) (Award CCF-0939370)

United States. Air Force Office of Scientific Research (Award FA9550-13-1-0042)


無相關資訊


無相關資訊

 

計畫贊助者: