Energy efficient and robust allocation of interdependent tasks on mobile ad hoc computational grid

A mobile ad hoc computational grid is a distributed computing infrastructure that allows mobile nodes to share computing resources in a mobile ad hoc environment. Compared to traditional distributed systems such as grids and clouds, resource allocation in mobile ad hoc computational grids is not straightforward because of node mobility, limited battery power and an infrastructure‐less network environment. The existing schemes are either based on a decentralized architecture that results in poor allocation decisions or assume independent tasks. This paper presents a scheme that allocates interdependent tasks and aims to reduce task completion time and the amount of energy consumed in transmission of data. This scheme comprises two key algorithms: resource selection and resource allocation. The resource selection algorithm is designed to select nodes that remain connected for a longer period, whereas the resource assignment or allocation algorithm is developed to allocate interdependent tasks to the nodes that are accessible at the minimum transmission power. The scheme is based on a hybrid architecture that results in effective allocation decisions, reduces the communication cost associated with the exchange of control information, and distributes the processing burden among the nodes. The paper also investigates the relationship between the data transfer time and transmission energy consumption and presents a power‐based routing protocol to reduce data transfer costs and transmission energy consumption. Copyright © 2014 John Wiley & Sons, Ltd.     

基于群智能的P2P计算网格负载均衡算法

对等网络(P2P)计算网格是采用非集中控制的动态网络环境，在P2P网络环境的各个对等节点间均匀分配任务是网格计算的重要研究内容。传统C/S模式的负载均衡算法无法适用于分布式且动态变化的P2P网络。文章提出了一种基于群智能和多代理技术的P2P网络负载均衡算法，设计并实现了基于蚁群优化算法的分布式作业调度策略。仿真结果表明该算法是合理而有效的。     

A distributed approach to node clustering in decentralized peer-to-peer networks

Connectivity-based node clustering has wide-ranging applications in decentralized peer-to-peer (P2P) networks such as P2P file sharing systems, mobile ad-hoc networks, P2P sensor networks, and so forth. This paper describes a connectivity-based distributed node clustering scheme (CDC). This scheme presents a scalable and efficient solution for discovering connectivity-based clusters in peer networks. In contrast to centralized graph clustering algorithms, the CDC scheme is completely decentralized and it only assumes the knowledge of neighbor nodes instead of requiring a global knowledge of the network (graph) to be available. An important feature of the CDC scheme is its ability to cluster the entire network automatically or to discover clusters around a given set of nodes. To cope with the typical dynamics of P2P networks, we provide mechanisms to allow new nodes to be incorporated into appropriate existing clusters and to gracefully handle the departure of nodes in the clusters. These mechanisms enable the CDC scheme to be extensible and adaptable in the sense that the clustering structure of the network adjusts automatically as nodes join or leave the system. We provide detailed experimental evaluations of the CDC scheme, addressing its effectiveness in discovering good quality clusters and handling the node dynamics. We further study the types of topologies that can benefit best from the connectivity-based distributed clustering algorithms like CDC. Our experiments show that utilizing message-based connectivity structure can considerably reduce the messaging cost and provide better utilization of resources, which in turn improves the quality of service of the applications executing over decentralized peer-to-peer networks.     

Practical load balancing for content requests in peer-to-peer networks

This paper studies the problem of balancing the demand for content in a peer-to-peer network across heterogeneous peer nodes that hold replicas of the content. Previous decentralized load balancing techniques in distributed systems base their decisions on periodic updates containing information about load or available capacity observed at the serving entities. We show that these techniques do not work well in the peer-to-peer context; either they do not address peer node heterogeneity, or they suffer from significant load oscillations which result in unutilized capacity. We propose a new decentralized algorithm, Max-Cap, based on the maximum inherent capacities of the replica nodes. We show that unlike previous algorithms, it is not tied to the timeliness or frequency of updates, and consequently requires significantly less update overhead. Yet, Max-Cap can handle the heterogeneity of a peer-to-peer environment without suffering from load oscillations. Mema Roussopoulos is an Assistant Professor of Computer Science on the Gordon McKay Endowment at Harvard University. Before joining Harvard, she was a Postdoctoral Fellow in the Computer Science Department at Stanford University. She received her PhD and Master’s degrees in Computer Science from Stanford, and her Bachelor’s degree in Computer Science from the University of Maryland at College Park. Her interests are in the areas of distributed systems, networking, and mobile and wireless computing. Mary Baker is a Senior Research Scientist at HP Labs. Her research interests include distributed systems, networks, mobile systems, security, and digital preservation. Before joining HP Labs she was on the faculty of the computer science department at Stanford University where she ran the MosquitoNet project. She received her PhD from the University of California at Berkeley.     

异构云平台中基于多层架构的动态循环调度方案

针对现有分布式循环自调度方案在异构云平台中存在负载不平衡等问题,提出一种基于多层架构的分层分布式动态循环调度方案。首先,通过HPLS算法来评估计算环境中各Worker节点的计算速度。然后,在传统自调度方案中融入节点计算速度,构建一种能够处理异构环境的调度方案,提高负载平衡能力。最后,将计算系统构建成一个由SuperMaster,Master和Worker节点组成的多层架构,利用层次化方法来解决传统Master-Worker架构中单个Master节点的瓶颈问题,用来提高任务分配效率。仿真实验结果表明,提出的方案能够有效提高云平台的计算效率。     

分布式空间信息的对等协同混合发现模型*

海量空间信息的处理需要分布式协同工作的GIS平台的支持,为了解决经典的分散式结构化的分布式哈希表逻辑网络结构增加的延时和在构建哈希表的过程中逻辑覆盖网络往往和物理网络不一致的问题,提出一种分布式空间信息的对等协同混合发现模型。基于空间资源发现代理节点和普通邻居节点,该模型实现了集中式的全局空间资源发现模型与分散式结构化的分布式哈希表模型之间的自动切换,能够自适应地调整空间资源的逻辑网络结构以提供更好的性能。基于节点交换机制,设计了构建路由表和降低延时的算法,通过发现有利于覆盖网络和物理网络匹配的节点交换来     

A dynamic programming approach: Improving the performance of wireless networks

Traditional wireless networks focus on transparent data transmission where the data are processed at either the source or destination nodes. In contrast, the proposed approach aims at distributing data processing among the nodes in the network thus providing a higher processing capability than a single device. Moreover, energy consumption is balanced in the proposed scheme since the energy intensive processing will be distributed among the nodes. The performance of a wireless network is dependent on a number of factors including the available energy, energy–efficiency, data processing delay, transmission delay, routing decisions, security architecture etc. Typical existing distributed processing schemes have a fixed node or node type assigned to the processing at the design phase, for example a cluster head in wireless sensor networks aggregating the data. In contrast, the proposed approach aims to virtualize the processing, energy, and communication resources of the entire heterogeneous network and dynamically distribute processing steps along the communication path while optimizing performance. Moreover, the security of the communication is considered an important factor in the decision to either process or forward the data. Overall, the proposed scheme creates a wireless “computing cloud” where the processing tasks are dynamically assigned to the nodes using the Dynamic Programming (DP) methodology. The processing and transmission decisions are analytically derived from network models in order to optimize the utilization of the network resources including: available energy, processing capacity, security overhead, bandwidth etc. The proposed DP-based scheme is mathematically derived thus guaranteeing performance. Moreover, the scheme is verified through network simulations.     

面向分布式协同设计的对等信息共享系统

为了实现分布式协同设计中的共享信息快速检索以及多副本同步，提出了基于对等网结构的信息共享系统，给出了该信息共享系统的节点模型、管理策略及信息检索模型，提出了一种结合分布式哈希表和聚类的检索方法，保证了用户能够在协同设计系统中快速地精确检索和“盲目”检索，实现了系统的用户透明。为了保证分布式多副本同步，提出“对等锁”作为一致性维护方法。该文给出了系统的具体实现方法，并给出了实例。     

异构网络环境下最大化谱间距的拓扑设计

分布式平均共识和去中心化机器学习是具有广泛应用的去中心化计算方法.两种方法的收敛率主要由拓扑的谱间距所决定.节点网络环境的异构性包括节点带宽和节点间连接可用性的不同.异构网络环境对去中心化计算的效率提出了挑战.本文研究异构网络环境下最大化谱间距的拓扑设计问题,推导了谱间距针对拓扑任一条边的梯度,并设计了基于该梯度的增删边算法来构建目标拓扑.构建的拓扑具有更大谱间距,且各节点的数据通信时间相近.拓扑构建算法的性能在不同程度的异构网络环境下能够保持稳定,且生成的拓扑在分布式共识中以更快的收敛率和更短的时间达到收敛.基于该算法,本文进一步验证了最新发现的谱间距与去中心化机器学习收敛率的弱相关性.     

P2P计算网格路由和负载均衡算法

路由和负载均衡是P2P计算网格的两个技术难题,由于P2P网络的分布性和动态性,以及缺乏统一的中心控制,使得传统的路由和负载均衡算法不能应用于P2P网络。提出了一种源自蚁群智能的混合路由和负载均衡算法,通过移动代理,即人工蚂蚁在节点间移动时所释放的信息素来作为路由和任务调度的依据。仿真结果表明该算法是有效的,且适用于具有分散和自组织特性的P2P网络。     

基于区块链与云-边缘计算混合架构的车联网数据安全存储与共享方案

针对车联网（IoV）中云计算的高时延、数据泄漏和恶意车辆节点篡改数据等问题,提出了一种基于区块链与云-边缘计算混合架构的IoV数据安全存储与共享方案。首先,采用联盟链-私有链的双链去中心化存储结构来保障通信数据的安全;然后,利用基于身份的数字签密算法和基于离散中心二项分布的环签名方案来解决通信过程中的安全性问题;最后,提出了基于动态分层和信誉值评估的实用拜占庭容错机制（DRPBFT）,并将边缘计算技术与云计算技术相结合,从而解决了高时延问题。安全性分析结果表明,所提方案在信息共享过程中保证了数据的安全性和完整性。实验仿真和性能评估结果表明,DRPBFT的时延在6 s内,且有效地提高了系统的吞吐量。所提IoV方案有效地促进了车辆数据共享的积极性,使IoV系统更加高效稳定地运行,达到了IoV实时、高效的目的。     

k-DmeansWM:一种基于P2P网络的分布式聚类算法

传统的分布式聚类算法设立中心节点来实现聚类过程的控制,这不仅降低了系统可靠性,而且容易出现单点失效问题。提出一种基于P2P网络的分布式聚类算法k-Dmeans Without Master(简称k-DmeansWM),即采用对等分布的思想,摒弃中心节点,完全由对等节点来实现聚类过程的控制。理论分析与实验结果表明,k-DmeansWM在保证聚类准确性与效率的情况下,大大提高了系统的可靠性与扩展性。     

MapReduce框架下结合分布式编码计算的容错算法

随着分布式系统规模扩大及计算复杂度增加,分布式计算的平均故障修复时间和容错计算所产生的通信开销呈现日益上升趋势。结合分布式编码计算和副本冗余技术,提出一种新的容错算法。map节点应用分布式编码计算的思想,将数据冗余分配至多个计算节点创建编码中间结果,降低计算节点在shuffle阶段的数据传输量。reduce节点通过对接收到的编码中间结果进行解码,从而验证中间结果的正确性并得到最终计算结果。实验结果表明,在基于MapReduce的分布式计算框架下,与三模冗余和两阶段三模冗余容错算法相比,该算法在完成容错计算的同时能降低计算过程中的通信开销和平均故障修复时间,并提高分布式系统的可用性和可靠性。     

移动边缘计算环境下基于改进GPSR的VANET路由算法

针对车辆自组织网络(VANET,vehicular ad-hoc network)中现有路由协议存在的路由选择错误、丢包率较高、服务质量低等问题,提出了移动边缘计算环境下,结合改进贪婪周边无状态路由(GPSR,greedy perimeter stateless routing)和自适应链路质量评估的VANET路由算法;首先,结合边缘计算构建了VANET通信模型,对其车辆位置和速度进行系统的理论分析;将边缘计算架构应用于VANET能够有效缓解计算量大、与车辆有限且不均的资源分布之间的矛盾;然后,提出了基于节点移动速度和节点间距离的改进GPSR协议,通过自适应链路稳定性和链路传递速率评估来选择合适的中继节点,动态更新链路;通过SUMO仿真平台对路由算法的性能进行评估,实验结果表明,相对于其他算法,所提算法受车辆密度、交通流以及车辆相对速度的影响较小,且提高了分组传送率(车辆数为300时传送率达到92%),减少端到端延迟(交通流为5时延迟降低到1.5 s),从而降低了通信开销。     

Dynamic end-to-end capacity in IEEE 802.16 wireless mesh networks

The IEEE 802.16 standard defines mesh mode as one of its two operational modes in medium access control (MAC). In the mesh mode, peer-to-peer communication between subscriber stations (SSs) is allowed, and transmissions can be routed via other SSs across multiple hops. In such an IEEE 802.16 mesh network, accurate and reliable determination of dynamic link capacity and end-to-end capacity of a given multi-hop route is crucial for robust network control and management. The dynamic capacities are difficult to determine in a distributed system due to decentralized packet scheduling and interference between communicating nodes caused by the broadcast nature of radio propagation. In this paper, we first propose a method for computing the dynamic link capacity between two mesh nodes, and extend that to determine the dynamic end-to-end capacity bounds of a multi-hop route based on the concept of Bottleneck Zone. The physical deployments of networks are also considered in the capacity estimation. We demonstrate the effectiveness and accuracy of our methods for computing dynamic link capacity and end-to-end capacity bounds through extensive simulations.     

CONFIIT: a middleware for peer-to-peer computing

CONFIIT (Computation Over Network with Finite number of Independent and Irregular Tasks) is a purely decentralized peer-to-peer middleware for grid computing. This paper presents CONFIIT main features and how it deals with topology changes and communication faults. To illustrate CONFIIT operation, we demonstrate how the car-sequencing problem can be solved in a distributed environment.     

分布式深度学习通信架构的性能分析

近年来,深度学习技术的进步推动人工智能进入了一个新的发展时期.但是,海量的训练数据、超大规模的模型给深度学习带来了日益严峻的挑战,分布式深度学习应运而生,逐渐成为应对这一挑战的有效手段,而高效的参数通信架构是保证分布式深度学习性能的关键.针对传统分布式深度学习模型同步架构在大规模节点上并行训练的问题,首先,分析了集中式的Parameter Server和去中心化的Ring Allreduce这2种主流的参数通信架构的原理和性能.然后,在天河高性能GPU集群上基于Ten-sorFlow构建了2种分布式训练架构的对比测试环境.最后,以Parameter Server架构为基准线,测试了Ring Allreduce架构在GPU集群环境下训练AlexNet和ResNet-50的对比性能.实验结果表明,在使用32个GPU的情况下,Ring Allreduce架构扩展效率可达97％,相比Parameter Server架构,其分布式计算性能可提升30％,验证了Ring Allreduce架构具有更好的可扩展性.     

Partial Multinode Broadcast and Partial Exchange Algorithms for d-Dimensional Meshes

In this paper we consider the partial multinode broadcast and the partial exchange communication tasks in d-dimensional meshes. The partial multinode broadcast in an N-processor network is the task in which each of M ≤ N arbitrary nodes broadcasts a packet to all the remaining N − 1 nodes. Correspondingly, in the partial exchange there are M ≤ N nodes that wish to send a separate, personalized packet to each of the other nodes. We propose algorithms for the d-dimensional mesh network that execute the partial multinode broadcast and the partial exchange communication tasks in near-optimal time. No assumption is made concerning the locations of the M source nodes. The communication algorithms proposed are "on line" and distributed. We further look at a dynamic version of the broadcasting problem, where broadcast requests are generated at random times. In particular, we assume that the broadcast requests are generated at each node of the mesh according to a Poisson distribution with rate λ. Based on the partial multinode broadcast algorithm, we propose a dynamic decentralized scheme to execute the broadcasts in this dynamic environment. We find an upper bound on the average delay required to serve each broadcast. We prove that the algorithm is stable for network utilization ρ close to 1, and the average delay is of the order of the diameter for any load in the stability region.     

一种双参数拓扑推测方法

针对采用单一性能参数推测网络拓扑结构算法的问题, 如有效性与网络负载有关以及测量节点性能参数时大多需要节点间时钟的同步等, 在现有的测量方法基础上, 提出了一种不需要节点间时钟同步可以测量端到端时延抖动和丢包相关性的紧接分组对序列测量方法, 同时设计了一种综合端到端时延抖动和丢包相关性的双参数拓扑推测算法, 该算法能够适应不同的网络负载环境。最后通过NS-2仿真实验验证了该算法的有效性和准确性。     

基于主客观赋权的多属性空间节点选择算法

针对空间协作传输中单属性协作节点选择算法无法兼顾系统可靠性和生存时间的问题，引入多属性决策方法（MADM），综合考虑信道衰落等级、协作节点剩余能量和误码率三个属性对空间协作节点进行多属性评估，提出一种基于主客观赋权的多属性空间协作节点选择（SOW-CNS）算法。首先，根据信道受阴影衰落影响程度，建立两状态无线信道模型，分别为无阴影Loo信道衰落模型和有阴影Corazza信道衰落模型；其次，引入基于主客观赋权的多属性决策策略，使用层次分析法和信息熵法建立空间协作节点的主观属性权向量和客观属性权向量；然后，使用最大熵原理和离差和最大法计算主客观属性权向量；最后，利用主客观属性权向量与各节点的属性值计算各潜在节点的评价值，进而选出最佳协作节点参与空间信息协作传输。仿真结果表明，与传统最佳质量协作节点选择算法（BQ-CNS）、能量公平性协作节点选择算法（EF-CNS）和随机协作节点选择算法（R-CNS）相比，基于主客观赋权的多属性决策算法不仅降低系统误码率，而且能够获得更长的系统生存期。