Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models

The optimal scheduling problem in two queueing models arising in multihop radio networks with scheduled link activation is investigated. A tandem radio network is considered. Each node receives exogenous arriving packets which are stored in its unlimited capacity buffer. Links adjacent to the same node cannot transmit simultaneously because of radio interference constraints. The problem of link activation scheduling for minimum delay is studied for two different traffic types. In the first type all packets have a common destination that is one end-node of the tandem. In this case the system is modeled by a tandem queueing network with dependent servers. The server scheduling policy that minimizes the delay is obtained. In the second type of traffic, the destination of each packet is an immediate neighbor of the node at which the packet enters the network. In this case the system corresponds to a set of parallel queues with dependent servers. It is shown that the optimal policy activates the servers so that the maximum number of packets are served at each slot.     

On a class of packet-switching networks on an infinite graph

A class of open queueing networks with packet switching is discussed. The configuration graph of the network may be finite or infinite. The external messages are divided into standard pieces (packets) each of which is transmitted as a single message. The messages are addressed, as a rule, to nearest neighbours and thereby the network may be treated as a small perturbation of the collection of isolated servers. The switching rule adopted admits overtaking: packets which appeared later may reach the delivery node earlier. The transmission of a message is completed when its last packet reaches the destination node. The main result of this paper is that the network possesses a unique stationary working regime. Weak dependence properties of this regime are established as well as the continuity with respect to the parameters of the external message flows.     

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.     

CONNECTIVITY OF CARTESIAN PRODUCT DIGRAPHS AND FAULT-TOLERANT ROUTINGS OF GENERALIZED HYPERCUBE

ＣＯＮＮＥＣＴＩＶＩＴＹＯＦＣＡＲＴＥＳＩＡＮＰＲＯＤＵＣＴＤＩＧＲＡＰＨＳＡＮＤＦＡＵＬＴ┐ＴＯＬＥＲＡＮＴＲＯＵＴＩＮＧＳＯＦＧＥＮＥＲＡＬＩＺＥＤＨＹＰＥＲＣＵＢＥＸＵＪＵＮＭＩＮＧＡｂｓｔｒａｃｔ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｐｒｏｂｌｅｍ...     

Real-time data gathering in sensor networks

Wireless sensor networks represent a new generation of real-time traffic communications and high data rate sensor applications, such as structural health monitoring and control. We study some problems related to data gathering in sensor networks when the sensors collect the sensed data about their environment and this information should be delivered to a collecting central Base Station. We prove that scheduling messages through the network to minimize the maximal delivery time with restrictions on the total idle time allowed is NP-hard. We also refer to a special case of linear network topology for which we present two polynomial time optimization algorithms: One is for minimizing the maximal lateness and maximal delay, while the other is for minimizing the number of tardy messages.     

Some topological properties of star graphs: The surface area and volume

The star graph, as an interesting network topology, has been extensively studied in the past. In this paper, we address some of the combinatorial properties of the star graph. In particular, we consider the problem of calculating the surface area and volume of the star graph, and thus answering an open problem previously posed in the literature. The surface area of a sphere with radius i in a graph is the number of nodes in the graph whose distance from a given node is exactly i. The volume of a sphere with radius i in a graph is the number of nodes within distance i from the given node. In this paper, we derive explicit expressions to calculate the surface area and volume in the star graph.     

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.     

移位交换网的最优路由算法

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式     

Path delays in communication networks

A communication network is modelled by a weighted graph. The vertices of the graph represent stations with storage capabilities, while the edges of the graph represent communication channels (or other information processing media). Channel capacity weights are assigned to the edges of the network. The network is assumed to operate in a store-and-forward manner, so that when a channel is busy the messages directed into it are stored at the station, joining there a queue which is governed by a first-come first-served service discipline. Assuming messages, with fixed length, to arrive at random at the network, following the statistics of a Poisson point process, we calculate the statistical characteristics of the message time-delays along a path in a communication network. We solve for the steadystate distributions of the message waiting-times along the path, for the distribution of the overall message delay-time, for the average memory size requirements at the stations, as well as for other statistical characteristics of the message flow and the queueing processes along a communication path.     

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.     

Minimum broadcast tree decompositions

Recursive constructions for decomposing the complete directed graph D_n into minimum broadcast trees of order n are given, thereby showing the existence of such decompositions for all n. Such decompositions can be used for a routing system in a network where every participant has the ability to broadcast a message to the group; as each arc is used in only one tree, a participant’s further actions upon receipt of a message depend only on its sender, and so all routing information can be stored locally rather than in the message itself.     

Stable network topologies using the notion of covering

An alternative perspective to evaluate networks and network evolution is introduced, based on the notion of covering. For a particular node in a network covering captures the idea of being outperformed by another node in terms of, for example, visibility and possibility of information gathering. In this paper, we focus on networks where these subdued network positions do not exist. We call these networks stable. Within this set we identify the minimal stable networks, which frequently have a ‘bubble-like’ structure. Severing a link in such a network results in at least one of the nodes being covered. In a minimal stable network therefore all nodes cooperate to avoid that one of the nodes ends up in a subdued position. Our results can be applied to, for example, the design of (covert) communication networks and the dynamics of social and information networks.     

On the enrouting protocol problem under uncertainty

In this paper we present a two-stage stochastic mixed 0–1 dynamic multicommodity model and algorithm for determining the enrouting protocol in the telecommunications network under uncertainty. Given the network connectivity, node processing and buffer and arc flow capacity, the aim is to determine the outgoing arc for the information flow reaching a given node for each destination terminal node (i.e., obtaining the route to be followed by the information flow from each origin terminal node to each destination terminal node). The origin–destination (O–D) flow matrix is given by the number of information packets to be sent from the origin terminal nodes to the destination terminal nodes along a given time horizon, i.e., a call scale. The uncertainty in the O–D flow matrix is treated via a scenario tree approach. The main goal is to minimize a composite function of the expected lost information, a penalization of the deviation from the FIFO strategy on the information flow entering the network, and the expected number of nodes visited by the information packets. A mixture of an enrouting arc generation scheme and a genetic algorithm for obtaining the enrouting protocols over the scenarios is presented. The tool presented in this paper could be used for simulating the enrouting protocols to analyze the saturation of the network, but it has a time constraint for real time operation. Faster algorithms are needed to define the routing tables during the operation stage. Computational experience is reported.     

基于时隙ALOHA协议的数据传输二人随机博弈模型

在一个给定的拓扑网络中研究关于数据传输的二人随机博弈模型.两个局中人（源节点）试图通过一个公共节点向目的节点传输随机数据包,这些数据包被分为重要的数据包和不重要的数据包两类,假设每个局中人都有一个用于存储数据包的有限容量的缓冲器.通过构造数据传输的成本分摊和奖励体系,把这种动态的冲突控制过程建模为具有有限状态集合的随机博弈,研究局中人在这种随机博弈模型下的非合作以及合作行为.在非合作情形下,给出纳什均衡的求解算法;在合作情形下,选择Shapley值作为局中人支付总和的分配方案,并讨论其子博弈一致性,提出使得Shapley值为子博弈一致的分配补偿程序.     

A multicast routing algorithm based on searching in directed graph

Aiming at constructing a delay and delay variation bounded Steiner tree in the real-time streaming media communication, in this paper, we discuss a multicast routing algorithm based on searching a directed graph (MRASDH). During the process of the construction of the multicast tree, some nodes and links in the network topology do not affect the outcome of the constructed tree. Therefore, based on the thought of shrinking the search space through deleting these non-relative nodes and edges to the utmost, the ant algorithm is utilized to generate a directed sub-graph of the network topology for each destination node, in which each node owns a bounded out-degree. And all these sub-graphs can be merged into a new directed graph that serves as the new search space. In the new space, the simulated annealing algorithm is applied to obtain a multicast tree that satisfies the condition for the optimization. The performance analysis and simulation results demonstrate that this algorithm can effectively construct a delay and delay variation bounded multicast tree. They also show that the algorithm have lower time complexity than the current ones, which means a much better result would be achieved when the system scale rises greatly.     

Distributed computation of virtual coordinates for greedy routing in sensor networks

Sensor networks are emerging as a paradigm for future computing, but pose a number of challenges in the fields of networking and distributed computation. One challenge is to devise a greedy routing protocol—one that routes messages through the network using only information available at a node or its neighbors. Modeling the connectivity graph of a sensor network as a 3-connected planar graph, we describe how to compute on the network in a distributed and local manner a special geometric embedding of the graph. This embedding supports a geometric routing protocol called “greedy routing” based on the “virtual” coordinates of the nodes derived from the embedding.     

Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks

A wireless sensor network usually consists of a large number of sensor nodes deployed in a field. One of the major communication operations is to broadcast a message from one node to the rest of the others. In this paper, we adopt the conflict-free communication model and study how to compute a transmission schedule that determines when and where a node should forward the message so that all nodes could receive the message in minimum time. We give two approximation algorithms for this NP-hard problem that have better theoretically guaranteed performances than the existing algorithms. The proposed approach could be applied to some other similar problems.     

ALOHA networks: a game-theoretic approach

In this paper we consider a wireless network consisting of various nodes, where transmissions are regulated by the slotted ALOHA protocol. Nodes using the protocol behave autonomously, and decide at random whether to transmit in a particular time slot. Simultaneous transmissions by multiple nodes cause collisions, rendering the transmissions useless. Nodes can avoid collisions by cooperating, for example by exchanging control messages to coordinate their transmissions. We measure the network performance by the long-term average fraction of time slots in which a successful transmission takes place, and we are interested in how to allocate the performance gains obtained from cooperation among the nodes. To this end we define and analyze a cooperative ALOHA game. We show that this type of game is convex and we consider three solution concepts: the core, the Shapley value, and the compromise value. Furthermore, we develop a set of weighted gain splitting (WGS) allocation rules, and show that this set coincides with the core of the game. These WGS allocation rules can be used to provide an alternative characterization of the Shapley value. Finally, we analyze the sensitivity of the cooperative solution concepts with respect to changes in the wireless network.     

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).     

Isometric embedding in products of complete graphs

An isometric (i.e., distance-preserving) embedding of a connected graph G into a cartesian product of complete graphs is equivalent to a labelling of each vertex of G by a string of symbols of fixed length such that the distance between two vertices is equal to the Hamming distance between the corresponding strings. Such a labelling could provide an addressing scheme for a communications network, since it enables a message to find a shortest path to its destination using only local information.We show that any two such embeddings of the same graph G are essentially the same, and give a polynomial-time algorithm which will find such an embedding if it exists. In addition we characterize the graphs which are isometrically embeddable in powers of K₃.