f模式下广播网络的最佳源点集

所谓广播 ,就是将网络中一个成员所拥有的消息 ,沿着网络成员之间的通信线路传递给其它所有成员的过程 .称最初拥有消息的成员为源点 .从不同的源点广播一条消息所需的时间一般是不同的 .关于Whisper模式和 Shouting模式下树上的最佳源点与最佳源点对问题 ,已有相关文章进行过讨 .本文提出了比c(c≥ 1)广播模式更一般的 f 广播模式的概念 ,并从该模式出发 ,在树形网络中设计了寻找最佳源点和最佳 k(k≥ 2 )源点集的算法 .     

A branch and price algorithm for the minimum power multicasting problem in wireless sensor networks

The Minimum Power Multicast Problem arises in wireless sensor networks and consists in assigning a transmission power to each node of a network in such a way that the total power consumption over the network is minimized, while a source node is connected to a set of destination nodes, toward which a message has to be sent periodically. A new mixed integer programming model for the problem, based on paths, is presented. A practical exact algorithm based on column generation and branch and price is derived from this model. A comparison with state-of-the-art exact methods is presented, and it is shown that the new approach compares favorably to other algorithms when the number of destination nodes is moderate. Under this condition, the proposed method is able to solve previously unmanageable instances.     

树形广播网络的最佳源点和最佳源点对

广播就是通信风格中的某些已知消息的成员（称为源点）将消息传递给其它所有成员的过程．通信网络一般用图来描述．从不同的网络成员广播一条消息所需的最少时间一般是不同的．本文在树网络中设计了选取一个或一对源点使广播时间最短的算法，这样的一个或一对源点称为最佳源点或最佳源点对．     

Information spreading in Delay Tolerant Networks based on nodes’ behaviors

Information spreading in DTNs (Delay Tolerant Networks) adopts a store–carry–forward method, and nodes receive the message from others directly. However, it is hard to judge whether the information is safe in this communication mode. In this case, a node may observe other nodes’ behaviors. At present, there is no theoretical model to describe the varying rule of the nodes’ trusting level. In addition, due to the uncertainty of the connectivity in DTN, a node is hard to get the global state of the network. Therefore, a rational model about the node’s trusting level should be a function of the node’s own observing result. For example, if a node finds k nodes carrying a message, it may trust the information with probability p(k). This paper does not explore the real distribution of p(k), but instead presents a unifying theoretical framework to evaluate the performance of the information spreading in above case. This framework is an extension of the traditional SI (susceptible-infected) model, and is useful when p(k) conforms to any distribution. Simulations based on both synthetic and real motion traces show the accuracy of the framework. Finally, we explore the impact of the nodes’ behaviors based on certain special distributions through numerical results.     

Location-aided routing with uncertainty in mobile ad hoc networks: A stochastic semidefinite programming approach

We study location-aided routing under mobility in wireless ad hoc networks. Due to node mobility, the network topology changes continuously, and clearly there exists an intricate tradeoff between the message passing overhead and the latency in the route discovery process. Aiming to obtain a clear understanding of this tradeoff, we use stochastic semidefinite programming (SSDP), a newly developed optimization model, to deal with the location uncertainty associated with node mobility. In particular, we model both the speed and the direction of node movement by random variables and construct random ellipses accordingly to better capture the location uncertainty and the heterogeneity across different nodes. Based on SSDP, we propose a stochastic location-aided routing (SLAR) strategy to optimize the tradeoff between the message passing overhead and the latency. Our results reveal that in general SLAR can significantly reduce the overall overhead than existing deterministic algorithms, simply because the location uncertainty in the routing problem is better captured by the SSDP model.     

Cache placement in sensor networks under an update cost constraint

In this paper, we address an optimization problem that arises in the context of cache placement in sensor networks. In particular, we consider the cache placement problem where the goal is to determine a set of nodes in the network to cache/store the given data item, such that the overall communication cost incurred in accessing the item is minimized, under the constraint that the total communication cost in updating the selected caches is less than a given constant. In our network model, there is a single server (containing the original copy of the data item) and multiple client nodes (that wish to access the data item). For various settings of the problem, we design optimal, near-optimal, heuristic-based, and distributed algorithms, and evaluate their performance through simulations on randomly generated sensor networks.     

Relay placement for fault tolerance in wireless networks in higher dimensions

In this paper we consider the problem of adding the smallest number of additional (relay) nodes to a network of static nodes with limited communication range so that the induced communication graph is 2-connected (we consider both edge and vertex connectivity). The problem is NP-hard. We develop algorithms that find close to optimal solutions for both edge and vertex connectivity. We prove the algorithms have an approximation ratio of 2M for nodes distributed in a d-dimensional Euclidean space, where M is the maximum node degree of a Minimum Spanning Tree in d dimensions using Euclidean metrics. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions (obstacles).     

树网络上f模式最优广播问题的线性算法

网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法.     

无中心优化的算子分裂方法

在某些多智能体系统中,由于受到通讯等因素的限制,单个智能体只能进行本地计算,再与相邻智能体交换数据.与传统的并行和分布式计算不同,这种数据交换方式不再使用中心节点或者共享内存,而仅限于相邻节点之间.这种通过局部数据交换而实现全网目标的方式叫做无中心计算.比如,从任意的多个数开始,所有智能体通过不断地计算其局部平均,就都能收敛到这些数的平均值.无中心计算有不易形成通讯和计算瓶颈的优点,更适合分布的节点,因此受到一些应用的欢迎. 本文介绍求解一致最优化问题的若干无中心算法.一致最优化问题的目标是全网所有节点的变量收敛到同一个、并使所有目标函数之和最小的值.我们可以通过推广求平均的无中心方法去实现这个目标,但是得到算法比普通（有中心的）优化算法收敛得更慢,有阶数差距.近年来,一些新的无中心算法弥补了这个阶数差距.本文采用算子分裂的统一框架,以比这些算法原文更为简单的形式介绍这些方法.     

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node.We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set.We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.     

Optimal gathering protocols on paths under interference constraints

We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d≥1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for 1≤d≤4, in the second case.     

Multiple UAVs path planning algorithms: a comparative study

Unmanned aerial vehicles (UAVs) are used in team for detecting targets and keeping them in its sensor range. There are various algorithms available for searching and monitoring targets. The complexity of the search algorithm increases if the number of nodes is increased. This paper focuses on multi UAVs path planning and Path Finding algorithms. Number of Path Finding and Search algorithms was applied to various environments, and their performance compared. The number of searches and also the computation time increases as the number of nodes increases. The various algorithms studied are Dijkstra’s algorithm, Bellman Ford’s algorithm, Floyd-Warshall’s algorithm and the AStar algorithm. These search algorithms were compared. The results show that the AStar algorithm performed better than the other search algorithms. These path finding algorithms were compared so that a path for communication can be established and monitored.     

Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures

Broadcasting is a process of transmitting a message held in one node of a communication network to all other nodes. Links of the network are subject to randomly and independently distributed faults with probability; faults are permanent and Byzantine, while all nodes are fault-free. In a unit of time, each node can communicate with at most one other node. We present a broadcasting algorithm which works fornnodes in timeO(log n) with probability of correctness exceeding 1 − 1/n, for sufficiently largen.     

Scalable and fault tolerant orthogonalization based on randomized distributed data aggregation

The construction of distributed algorithms for matrix computations built on top of distributed data aggregation algorithms with randomized communication schedules is investigated. For this purpose, a new aggregation algorithm for summing or averaging distributed values, the push-flow algorithm, is developed, which achieves superior resilience properties with respect to failures compared to existing aggregation methods. It is illustrated that on a hypercube topology it asymptotically requires the same number of iterations as the optimal all-to-all reduction operation and that it scales well with the number of nodes. Orthogonalization is studied as a prototypical matrix computation task. A new fault tolerant distributed orthogonalization method rdmGS, which can produce accurate results even in the presence of node failures, is built on top of distributed data aggregation algorithms.     

Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks

A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648（rmax/rmin）^2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most （1 ＋ 2rmax/rmin）^2＋32, Moreover, under the proposed scheduling each node just needs to forward a message at most once.     

A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks

Genetic algorithms and other evolutionary algorithms have been successfully applied to solve constrained minimum spanning tree problems in a variety of communication network design problems. In this paper, we enlarge the application of these types of algorithms by presenting a multi-population hybrid genetic algorithm to another communication design problem. This new problem is modeled through a hop-constrained minimum spanning tree also exhibiting the characteristic of flows. All nodes, except for the root node, have a nonnegative flow requirement. In addition to the fixed charge costs, nonlinear flow dependent costs are also considered. This problem is an extension of the well know NP-hard hop-constrained Minimum Spanning Tree problem and we have termed it hop-constrained minimum cost flow spanning tree problem. The efficiency and effectiveness of the proposed method can be seen from the computational results reported.     

Two new algorithms for the Min-Power Broadcast problem in static ad hoc networks

In this paper we address the Min-Power Broadcast problem in wireless ad hoc networks. Given a network with an identified source node w, the Min-Power Broadcast (MPB) problem is to assign transmission range to each node such that communication from w to other nodes is possible and the total energy consumption is minimized.

As the problem is NP-Hard we first propose a simulated annealing algorithm for the MPB problem. Utilizing a special node selection mechanism in its neighborhood structure the algorithm is designed in a way enabling an efficient power consumption evaluation and search for neighboring solutions. We then combine the algorithm with a decomposition approach to enhance its performance. This is achieved by decomposing the master problem and performing metropolis chain of the simulated annealing only on the much smaller subproblems resulting from decomposition. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed algorithms.     

Minimal spanning trees with a constraint on the number of leaves

In this paper we discuss minimal spanning trees with a constraint on the number of leaves. Tree topologies appear when designing centralized terminal networks. The constraint on the number of leaves arises because the software and hardware associated to each terminal differs accordingly with its position in the tree. Usually, the software and hardware associated to a “degree-1” terminal is cheaper than the software and hardware used in the remaining terminals because for any intermediate terminal j one needs to check if the arrival message is destined to that node or to any other node located after node j. As a consequence, that particular terminal needs software and hardware for message routing. On the other hand, such equipment is not needed in “degree-1” terminals. Assuming that the hardware and software for message routing in the nodes is already available, the above discussion motivates a constraint stating that a tree solution has to contain exactly a certain number of “degree-1” terminals. We present two different formulations for this problem and some lower bounding schemes derived from them. We discuss a simple local-exchange heuristic and present computational results taken from a set of complete graphs with up to 40 nodes. Integer Linear Programming formulations for related problems are also discussed at the end.     

Routing tree maintenance based on trajectory prediction in mobile sensor networks

With the wireless sensor networks (WSNs) becoming extremely widely used, mobile sensor networks (MSNs) have recently attracted more and more researchers’ attention. Existing routing tree maintenance methods used for query processing are based on static WSNs, most of which are not directly applicable to MSNs due to the unique characteristic of mobility. In particular, sensor nodes are always moving in real world, which seriously affects the stability of the routing tree. Therefore, in this paper, we propose a novel method, named routing tree maintenance based on trajectory prediction in mobile sensor networks (RTTP), to guarantee a long term stability of routing tree. At first, we establish a trajectory prediction model based on extreme learning machine (ELM), by which we can predict sensor node’s trajectory to choose an appropriate parent node for each non-effective node. Then, an Improved version of RTTP method (I-RTTP) that using probabilistic method to minimize the error and improve the accuracy is proposed, to improve the performance of RTTP. Therefore, the state of the routing tree in MSNs can be made more stable. Finally, extensive experimental results show that RTTP and I-RTTP can effectively improve the stability of routing tree and greatly reduce energy consumption of mobile sensor nodes.     

The energy-constrained quickest path problem

This paper addresses a variant of the quickest path problem in which each arc has an additional parameter associated to it representing the energy consumed during the transmission along the arc while each node is endowed with a limited power to transmit messages. The aim of the energy-constrained quickest path problem is to obtain a quickest path whose nodes are able to support the transmission of a message of a known size. After introducing the problem and proving the main theoretical results, a polynomial algorithm is proposed to solve the problem based on computing shortest paths in a sequence of subnetworks of the original network. In the second part of the paper, the bi-objective variant of this problem is considered in which the objectives are the transmission time and the total energy used. An exact algorithm is proposed to find a complete set of efficient paths. The computational experiments carried out show the performance of both algorithms.