• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Selected Topics in Signal Processing, IEEE Journal of >A Token-Based Approach for Distributed Computation in Sensor Networks
【24h】

A Token-Based Approach for Distributed Computation in Sensor Networks

机译：传感器网络中基于令牌的分布式计算方法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider distributed algorithms for data aggregation and function computation in sensor networks. The algorithms perform pairwise computations along edges of an underlying communication graph. A token is associated with each sensor node, which acts as a transmission permit. Nodes with active tokens have transmission permits; they generate messages at a constant rate and send each message to a randomly selected neighbor. By using different strategies to control the transmission permits we can obtain tradeoffs between message and time complexity. Gossip corresponds to the case when all nodes have permits all the time. We study algorithms where permits are revoked after transmission and restored upon reception. Examples of such algorithms include Simple-Random Walk (SRW), Coalescent-Random-Walk (CRW), and Controlled Flooding (CFLD) and their hybrid variants. SRW has a single node permit, which is passed on in the network. CRW, initially has a permit for each node but these permits are revoked gradually. The final result for SRW and CRW resides at a single (or few) random node(s) making a direct comparison with GOSSIP difficult. A hybrid two-phase algorithm switching from CRW to CFLD at a suitable predetermined time can be employed to achieve consensus. We show that such hybrid variants achieve significant gains in both message and time complexity. The per-node message complexity for n-node graphs, such as 2-D mesh, torii, and random geometric graphs, scales as $O(polylog(n))$ and the corresponding time complexity scales as $O(n)$. The reduced per-node message complexity leads to reduced energy utilization in sensor networks.
机译：我们考虑用于传感器网络中数据聚合和功能计算的分布式算法。该算法沿着基础通信图的边缘执行成对计算。令牌与每个传感器节点关联，充当传输许可。具有有效令牌的节点具有传输许可；它们以恒定的速率生成消息，并将每条消息发送到随机选择的邻居。通过使用不同的策略来控制传输许可，我们可以获得消息和时间复杂度之间的折衷。八卦对应于所有节点始终具有许可的情况。我们研究的算法是，许可证在发送后被吊销，在接收后被恢复。这种算法的示例包括简单随机漫游（SRW），合并随机漫游（CRW）和受控泛洪（CFLD）及其混合变体。 SRW具有单节点许可，该许可在网络中传递。 CRW最初对每个节点都有许可，但这些许可逐渐被撤销。 SRW和CRW的最终结果位于单个（或几个）随机节点上，因此很难与GOSSIP进行直接比较。可以采用在适当的预定时间从CRW切换到CFLD的混合两阶段算法来达成共识。我们表明，这种混合变体在消息和时间复杂度上都取得了显着的进步。 n节点图（例如2-D网格，torii和随机几何图）的每个节点消息复杂度缩放为$ O（polylog（n））$，相应的时间复杂度缩放为$ O（n）$ 。减少的每节点消息复杂度导致减少传感器网络中的能量利用。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号