Optimal NODUP all-to-all broadcast schemes in distributed computingsystems

Broadcast, referring to a process of information dissemination in a distributed system whereby a message originating from a certain node is sent to all other nodes in the system, is a very important issue in distributed computing. All-to-all broadcast means the process by which every node broadcasts its certain piece of information to all other nodes. In this paper, we first develop the optimal all-to-all broadcast scheme for the case of one-port communication, which means that each node can only send out one message in one communication step, and then, extend our results to the case of multi-port communication, i.e., k-port communication, meaning that each node can send out k messages in one communication step. We prove that the proposed schemes are optimal for the model considered in the sense that they not only require the minimal number of communication steps, but also incur the minimal number of messages     

基于链路重构策略的网络抗毁性优化研究

网络抗毁性优化是目前通信网络研究的重要领域。为实现对通信网络的抗毁性优化,提高网络抗打击能力,对网络抗毁性与网络聚合度之间的关系进行分析,利用该结论提出了网络抗毁性优化的链路重构策略。一是通过对传统HBF-α算法链路重构策略的调整,提高了网络优化效果,且算法复杂度低、收敛速度快、效率较高;二是结合部分通信网络实际要求,提出了保证节点度不变的重构策略,以网络聚合度为目标函数,使用模拟退火算法有效解决了HBF-α策略中局部最优解问题。并分析对比两种优化方案的优化程度以及时间开销。对于规模较大,且各节点建链能力较强的网络采用方案一优化;对规模较小,且各节点建链能力有限的网络采用方案二优化,可以达到较好的网络抗毁性优化效果。     

State estimation over a communication network： measurement or estimate communication？

In this paper we consider the problem of state estimation over a communication network. Using estimation quality as a metric, two communication schemes are studied and compared. In scheme one, each sensor node communicates its measurement data to the remote estimator, while in scheme two, each sensor node communicates its local state estimate to the remote estimator. We show that with perfect communication link, if the sensor has unlimited computation capability, the two schemes produce the same estimate at the estimator, and if the sensor has limited computation capability, scheme one is always better than scheme two. On the other hand, when data packet drops occur over the communication link, we show that if the sensor has unlimited computation capability, scheme two always outperforms scheme one, and if the sensor has limited computation capability, we show that in general there exists a critical packet arrival rate, above which scheme one outperforms scheme two. Simulations are provided to demonstrate the two schemes under various circumstances.     

无线 Ad hoc 网络和传感网络中基于位置的、可靠的无信标传输路由方法

Existing position-based routing algorithms, where packets are forwarded in the geographic direction of the destination, normally require that the forwarding node should know the positions of all neighbors in its transmission range. This information on direct neighbors is gained by observing beacon messages that each node sends out periodically. Several beaconless greedy routing schemes have been proposed recently. However, none of the existing beaconless schemes guarantee the delivery of packets. Moreover, they incur communication overhead by sending excessive control messages or by broadcasting data packets. In this paper, we describe how existing localized position based routing schemes that guarantee delivery can be made beaconless, while preserving the same routes. In our guaranteed delivery beaconless routing scheme, the next hop is selected through the use of control RTS/CTS messages and biased timeouts. In greedy mode, the neighbor closest to destination responds first. In recovery mode, nodes closer to the source will select shorter timeouts, so that other neighbors, overhearing CTS packets, can eliminate their own CTS packets if they realize that their link to the source is not part of Gabriel graph. Nodes also cancel their packets after receiving data message sent by source to the selected neighbor. We analyze the behavior of our scheme on our simulation environment assuming ideal MAC, following GOAFR+ and GFG routing schemes. Our results demonstrate low communication overhead in addition to guaranteed delivery.     

Optimal total exchange in Cayley graphs

Consider an interconnection network and the following situation: Every node needs to send a different message to every other node. This is the total exchange or all-to-all personalized communication problem, one of a number of information dissemination problems known as collective communications. Under the assumption that a node can send and receive only one message at each step (single-port model), it is seen that the minimum time required to solve the problem is governed by the status (or total distance) of the nodes in the network. We present a time-optimal solution for any Cayley network. Rings, hypercubes, cube-connected cycles, and butterflies are some well-known Cayley networks which can take advantage of our method. The solution is based on a class of algorithms which we call node-invariant algorithms and which behave uniformly across the network     

A Message Scheduling Scheme for All-to-All Personalized Communication on Ethernet Switched Clusters

We develop a message scheduling scheme for efficiently realizing all-to-all personalized communication (AAPC) on Ethernet switched clusters with one or more switches. To avoid network contention and achieve high performance, the message scheduling scheme partitions AAPC into phases such that 1) there is no network contention within each phase and 2) the number of phases is minimum. Thus, realizing AAPC with the contention-free phases computed by the message scheduling algorithm can potentially achieve the minimum communication completion time. In practice, phased AAPC schemes must introduce synchronizations to separate messages in different phases. We investigate various synchronization mechanisms and various methods for incorporating synchronizations into the AAPC phases. Experimental results show that the message scheduling-based AAPC implementations with proper synchronization consistently achieve high performance on clusters with many different network topologies when the message size is large     

ANALYSIS OF GOSSIPING ALGORITHMS WITH RESTRICTED BUFFERS

In this paper we present a new algorithm for gossiping in distributed-memory parallel architectures whose interconnection network is a two-dimensional torus. The results are presented for odd-sized square torus, but the extensions are discussed at the end of the paper. The gossiping communication routine corresponds to simultaneous broadcasts at each node. In this study we assume a store-and-forward routing mechanism where all processors send a message of same length on each link during the time step. As we briefly discuss at the end, this holds also for circuit-switched routing for large messages.

The main result of this work is to establish a general lower bound for gossiping in a square torus and to analyze the influence of buffering. After a brief discussion of the existing solutions, we present the principle of a new algorithm. Then, we study its complexity with restricted buffers. This new algorithm is compared with the existing gossiping algorithms from its buffering capabilities and is found to be superior.     

Dominating sets and neighbor elimination-based broadcastingalgorithms in wireless networks

In a multihop wireless network, each node has a transmission radius and is able to send a message to all of its neighbors that are located within the radius. In a broadcasting task, a source node sends the same message to all the nodes in the network. In this paper, we propose to significantly reduce or eliminate the communication overhead of a broadcasting task by applying the concept of localized dominating sets. Their maintenance does not require any communication overhead in addition to maintaining positions of neighboring nodes. Retransmissions by only internal nodes in a dominating set is sufficient for reliable broadcasting. Existing dominating sets are improved by using node degrees instead of their ids as primary keys. We also propose to eliminate neighbors that already received the message and rebroadcast only if the list of neighbors that might need the message is nonempty. A retransmission after negative acknowledgements scheme is also described. The important features of the proposed algorithms are their reliability (reaching all nodes in the absence of message collisions), significant rebroadcast savings, and their localized and parameterless behavior. The reduction in communication overhead for the broadcasting task is measured experimentally. Dominating set based broadcasting, enhanced by a neighbor elimination scheme and highest degree key, provides reliable broadcast with ⩽53 percent of node retransmissions (on random unit graphs with 100 nodes) for all average degrees d. Critical d is around 4, with <48 percent for ⩽3, ⩽40 percent for d⩾10, and ⩽20 percent for d⩾25. The proposed methods are better than existing ones in all considered aspects: reliability, rebroadcast savings, and maintenance communication overhead. In particular, the cluster structure is inefficient for broadcasting because of considerable communication overhead for maintaining the structure and is also inferior in terms of rebroadcast savings     

带式输送机故障定位系统网关的设计

以带式输送机故障定位系统为应用背景,提出了一种基于STM32F103VE微处理器的CAN总线与Profibus-DP总线网关的设计方案。该网关在CAN网络中作为一个CAN通信节点,在Profibus-DP网络中作为一个从站;带式输送机沿线分布若干个CAN检测节点,每个节点负责检测其段内的4种传感器设备采集的实时数据,如果检测到故障信息,CAN检测节点就会向网关发送故障信息报文,网关接收CAN检测节点发送的报文并进行存储;当网关与Profibus-DP主站连通后,作为Profibus-DP从站的网关可以通过查询方式把故障信息报文传送到Profibus-DP主站中,从而实现故障定位功能。实际应用表明,该网关运行稳定、可靠,实现了带式输送机故障定位系统中CAN总线及Profibus-DP总线的互联。     

利用匿名通信的匿名电子拍卖协议

为了保护电子拍卖中竞拍者的身份隐私,提出了一个基于匿名通信的匿名电子拍卖协议.该协议在密封式拍卖方式的基础上,采用匿名通信模型进行通信.在整个通信过程中,竞拍者随机选取网络中的一个节点进行数据的转发,然后该中转节点再以概率Pf将数据发送给下一个中转节点或是以概率1-Pf将数据发送给拍卖服务器,下一个中转节点重复该中转节点的过程,直到最后一个中转节点将数据发送给拍卖服务器.在发送数据的过程中,使用AES算法和RSA算法分别对消息和密钥进行混合加密解密操作.数据经过多次转发最终到达拍卖服务器.拍卖服务器、任意的中转节点和攻击者都不可能获取竞拍者的身份和位置信息.任意的中转节点和攻击者都不可能获取竞拍者的竞标信息.相比较Crowds、Tor以及其改进的方案,本方案在通信过程中不需要提前建立链路,避免了路由路径上节点建好链路后节点故障而引起的通信失败.通信过程中所有节点都是对等的,并且整个路由路径中不依赖于某些特殊节点,因此该协议实现了网络流量的负载均衡且大大提高了网络的健壮性.理论分析和实验结果表明,该协议不仅稳定性较好,而且可以在较低的通信和计算代价下获得较好的匿名效果.     

一种用混沌实现相互确认的安全通信方案

文章提出了一种利用混沌系统实现安全通信的方案。通信双方互相发送一次信息来确认对方身份,同时实现密钥的安全传输,从而实现安全通信,并且还可以发现攻击者的非法篡改。理论分析和数值模拟表明该方案有较高的安全性。     

一种无线传感器网络中自主选择簇头的聚类算法

在无线传感网络中,传感器节点要定期向基站发送收集的数据。为了支持数据汇总,通过高效的网络组织将节点划分成若干簇。在这种类型的系统中,随着簇头的轮转,每个簇中的簇头选择方法是最具有挑战性的问题,有效的簇头选择算法可以提高网络的续航时间,并减少在WSN中的节点之间的通信开销。提出一个簇内民主方式选举算法来选择簇中的节点作为簇头,用MatLab对算法进行仿真,证明该算法的性能可以有效改善网络的性能。     

On the complexity of buffer allocation in message passing systems

Message passing programs commonly use message buffers to avoid unnecessary synchronizations and to improve performance by overlapping communication with computation. Unfortunately, using buffers can introduce portability problems and can lead to deadlock problems on systems without a sufficient number of message buffers.We explore a variety of problems related to buffer allocation for safe and efficient execution of message passing programs. We show that determining the minimum number of message buffers or verifying that each process has a sufficient number of message buffers are intractable problems. However, we give a polynomial time algorithm to determine the minimum number of message buffers needed to ensure that no send operation is unnecessarily delayed due to lack of message buffers. We extend these results to several different buffering schemes, which in some cases make the problems tractable.     

一种改进的源节点位置隐私保护方法

当传感器网络中存在一个全局监听者的情况下,为了保护源节点的位置安全,文中提出了一种周期性发送干扰数据的算法。网络中的节点周期性地发送干扰数据包,将真实数据混淆在其中,攻击者无法判断真实数据的流向,从而保护了源节点的安全。同时,文中提出在每个节点中设立数据门限的思想,当节点中的数据超过一定门限值,将根据一定策略暂缓发送干扰数据,从而防止网络拥塞等状况的出现,同时能平衡网络的流量状况,节省资源带宽。从网络流量分析结果可知,该算法有效地保护了源节点的安全。     

Asynchronous privacy-preserving iterative computation on peer-to-peer networks

Privacy preserving algorithms allow several participants to compute a global function collaboratively without revealing local information to each other. Examples of applications include trust management, collaborative filtering, and ranking algorithms such as PageRank. Most solutions that can be proven to be privacy preserving theoretically are not appropriate for highly unreliable, large scale, distributed environments such as peer-to-peer (P2P) networks because they either require centralized components, or a high degree of synchronism among the participants. At the same time, in P2P networks privacy preservation is becoming a key requirement. Here, we propose an asynchronous privacy preserving communication layer for an important class of iterative computations in P2P networks, where each peer periodically computes a linear combination of data stored at its neighbors. Our algorithm tolerates realistic rates of message drop and delay, and node churn, and has a low communication overhead. We perform simulation experiments to compare our algorithm to related work. The problem we use as an example is power iteration (a method used to calculate the dominant eigenvector of a matrix), since eigenvector computation is at the core of several practical applications. We demonstrate that our novel algorithm also converges in the presence of realistic node churn, message drop rates and message delay, even when previous synchronized solutions are able to make almost no progress.     

基于消息认证混合同态签名的无线网络抗污染攻击方案

为提高无线网络抗污染攻击性能,提出一种基于消息认证混合同态签名的无线网络抗污染攻击方案。首先,采用有向多重图的源节点、非源节点集和链路集对无线网络编码过程进行模型构建,并考虑数据污染攻击和标签污染攻击2种类型的污染攻击建立网络抗污染模型;其次,利用MACs和D-MACs以及Sign同态签名方案,建立混合型的同态签名方案,实现对抗污染攻击模型的消息验证过程的改进,保证了每个MAC编码数据包内容的完整性,并提升了算法的执行效率;最后,通过在基于ASNC机制的实验模拟环境下,对所提算法在被污染节点百分比、流量累积分布和计算效率3个指标中的实验对比,验证了所提算法的性能优势。     

Privacy-aware routing in sensor networks

A typical sensor network application is to monitor objects, including wildlife, vehicles and events, in which information about an object is periodically sent back to the sink. Many times, the object needs to be protected for security reasons. However, an adversary can detect message flows and trace the message back to its source by moving in the reverse direction of the flows. This paper aims to maximize source location privacy, which is evaluated by the adversary’s traceback time, by designing routing protocols that distribute message flows to different routes. First, we give the performance bound for any routing scheme. Then, we present our routing schemes, which maximize the adversary’s average traceback time and achieve max–min traceback time given certain energy constraints. We then propose WRS, a suboptimal but practical privacy-aware routing scheme, and provide simulation results. Finally, we extend the discussion to an extreme adversary model, which allows the adversary to deploy an adversary sensor network to monitor the message routing activities. Accordingly, we propose a random schedule scheme to confuse the adversary. To reduce the message delivery time, we give an approximation algorithm for message routing.     

新的对抗全局窃听的安全网络编码方案

现有的对抗全局窃听攻击的安全网络编码方案存在引入了带宽开销、导致了很高的计算复杂度的问题,为了降低带宽开销并且提升实际编码效率,提出了一种新的对抗全局窃听的安全网络编码方案。对于编码域大小为q的网络编码,该方案利用密钥生成两个长度为q的置换序列,并利用置换序列对信源消息进行混合和替换,从而实现对抗全局窃听攻击。该方案只需在信源节点对信源消息进行加密,在中间节点不需作任何改变。由于该方案加密算法简单、编码复杂度低并且不需要预编码操作,因此该方案没有引入带宽开销且具有较高的实际编码效率。分析结果表明该方案不但可以抵抗唯密文攻击,对于已知明文攻击也有很好的抵抗效果。     

移动社会网络中基于活动的消息机会转发

针对移动社会网络中节点移动形成的成簇特性和节点参与活动表现的周期特点,提出了一种基于活动的消息机会转发算法（activity-based message opportunistic forwarding,简称AMOF）.算法思想是：当消息携带节点与目的节点存在相同活动时,选择消息交付概率高的中继节点转发消息;当消息携带节点与目的节点不存在相同活动时,选择消息间接交付概率高的链路来转发消息.仿真结果表明,与经典路由算法（如Epidemic,PRoPHET,CMOT和CMTS）比较,所提出的路由算法不仅能够提高消息的传输成功率,还能有效地降低传输时延和网络负载.     

Fast gossiping in square meshes/tori with bounded-size packets

Gossiping is a communication problem in which each node has a unique message (token) to be transmitted to every other node. The nodes exchange their tokens by means of packets. A solution to the problem is judged by how many rounds of packet sending are required. In this paper, we consider a version of the problem in which small-sized packets (each carrying exactly one token) are used, the links (edges) of the network are half-duplex (only one packet can flow through a link at a time), and the nodes are all-port (a node's incident edges can all be active at the same time). This is also known as the H* model. We study the model on a 2D square mesh and on a 2D square torus. An improved, asymptotically optimal algorithm for the mesh and an optimal algorithm for the torus are presented