Analyzing the Reliability of Degradable Networks

The reachability of a strongly connected network may be destroyed after link damage,Since many networds have directed links with the potential for reversal,the reachability may be restored by reversing the direction of links.In this paper,the reliability of a network that allows reversal of links in discussed.     

Improving the Reliability of Computer Communication Networks

For networks that are directed or can be represented by a directed network,reversing one or more of the uni-directional links may provide the ability to reconnect a network that has been disconnected by link failure.In this paper,a new approach to reconfigure such networks is proposed.We develop a linear time algorithm which,when reachability has been destroyed by the removal of a single link,optimally restores reachability through the reversal of selected links.Multi-link failure reconnectability is discussed and an algorithm with polynomial complexity is given which provides a nearly optimum solution to reconnect the network.We show that the reliability of a network that allows reversals is at least twice more than that in which reversals are not permitted.Unfortunately,the reconnection of some networks cannot be established.Therefore,we discuss the maximization of reachability of such networks so that each node can reach maximum number of the other nodes.     

Detecting and Locating Failures in Communication Networks

The connectivity of a strongly connected network may be destroyed after link damage.Since many networks are connected by directed links,the reachability may be restore by altering the direction of one or more of the links and thus reconfiguring the network.The location of the failed link ust first be determined.In this paper,we examine new methods to determine the location of failed links and nodes in networks.A routing test approach is proposed and the conditions under which communication networks may be tested are discussed Finally,an adaptive algorithm and a heuristic algorithm that can locate a single failed link or a single failed node are presented.     

Routing of multicast audio/video streams in reconfigurable WDM optical networks

Due to its low attenuation, fiber has become the medium of choice for point-to-point links. Using Wavelength-Division Multiplexing (WDM), many independent channels can be created in the same fiber. A network node equipped with a tunable optical transmitter can select any of these channels for sending data. An optical interconnection combines the signal from the various transmitters in the network, and makes it available to the optical receivers, which may also be tunable. By properly tuning transmitters and/or receivers, point-to-point links can be dynamically created and destroyed. Therefore, in a WDM network, the routing algorithm has an additional degree of freedom compared to traditional networks: it can modify the netowrk topology to create the routes. In this paper, we consider the problem of routing multicast audio/video streams in WDM networks and propose heuristic algorithms to solve it. The performance of these heuristics is evaluated in a number of scenarios, with a realistic traffic model, and from the evaluation we derive guidelines for usage of the proposed algorithms.This work was supported in part by NASA under grant NAG2-842, by the National Science Foundation under grant NCR-9016032 and by Pacific Bell. Ciro Noronha was supported by a graduate scholarship from FAPESP from Sept/89 to Aug/93 under grant 89/1658.     

基于路网可达性的交通控制子区划分方法研究

为了提高子区划分的效率,保证子区划分结果的合理性,提出了一种基于路网可达性的子区划分方法。以路口为顶点,路段为边,修正的路段阻抗为边权得到路网加权网络,通过权系数开关化转为非加权网络;采用[K]步可达矩阵来分析网络的可达性,以可达性最好的顶点为核心顶点,求解核心顶点的[K]步可达顶点群得到子区划分结果;以子区路网路段占有率方差为评价指标,对子区划分结果进行优化。以北京市亦庄林肯公园地区路网为例的仿真结果表明：基于路网可达性的子区划分,可以找到路网中关联最为紧密的顶点群,且以子区内部路段的占有率方差作为评价指标可以保证子区内部路段状态的相似性,为子区划分的优化提供指导。     

On the Convergence of Multicast Games in Directed Networks

We investigate the convergence of the price of anarchy after a limited number of moves in the classical multicast communication game when the underlying communication network is directed. Namely, a subset of nodes of the network are interested in receiving the transmission from a given source node and can share the cost of the used links according to fixed cost sharing methods. At each step, a single receiver is allowed to modify its communication strategy, that is to select a communication path from the source, and assuming a selfish or rational behavior, it will make a best response move, that is it will select a solution yielding the minimum possible payment or shared cost. We determine lower and upper bounds on the price of anarchy, that is the highest possible ratio among the overall cost of the links used by the receivers and the minimum possible cost realizing the required communications, after a limited number of moves under the fundamental Shapley cost sharing method. In particular, assuming that the initial set of connecting paths can be arbitrary, we show an $O(r\sqrt{r})We investigate the convergence of the price of anarchy after a limited number of moves in the classical multicast communication game when the underlying communication network is directed. Namely, a subset of nodes of the network are interested in receiving the transmission from a given source node and can share the cost of the used links according to fixed cost sharing methods. At each step, a single receiver is allowed to modify its communication strategy, that is to select a communication path from the source, and assuming a selfish or rational behavior, it will make a best response move, that is it will select a solution yielding the minimum possible payment or shared cost. We determine lower and upper bounds on the price of anarchy, that is the highest possible ratio among the overall cost of the links used by the receivers and the minimum possible cost realizing the required communications, after a limited number of moves under the fundamental Shapley cost sharing method. In particular, assuming that the initial set of connecting paths can be arbitrary, we show an O(r?r)O(r\sqrt{r}) upper bound on the price of anarchy after 2 rounds, during each of which all the receivers move exactly once, and a matching lower bound, that we also extend to W(r^k?{r})\Omega(r\sqrt[k]{r}) for any number k≥2 rounds, where r is the number of receivers. Similarly, exactly matching upper and lower bounds equal to r are determined for any number of rounds when starting from the empty state in which no path has been selected. Analogous results are obtained also with respect to other three natural cost sharing methods considered in the literature, that is the egalitarian, path-proportional and egalitarian-path proportional ones. Most results are also extended to the undirected case in which the communication links are bidirectional.     

大图上跳数受限的可达查询算法研究与优化

判断有向图上两个顶点之间是否存在一条路径是一个经典问题,而对于一些路由规划和图分析等实际应用,要求查找是否存在跳数受限的可达路径,这是一个变种的图可达查询问题.对于大图上跳数受限的查询算法,不仅仅要对大图查询的时间效率和空间效率进行权衡,而且还要利用跳数受限的特性进行优化.普通的可达查询算法存在小度数顶点索引项占用空间过多的问题,造成空间浪费严重.为此我们提出了一种面向跳数受限的2-hop部分索引方法,采用改进的索引方法并结合局部搜索,实现跳数受限的有效可达性查询.实验结果表明,在Orkut社交网络数据集上与已有算法相比,该算法索引空间节省了32％,同时查询时间略微增加,使得我们算法可以计算更大规模图的跳数受限可达问题.     

面向个性化推荐的两层混合图模型

A hybrid graph model for personalized recom- mendation, which is based on small world network and Bayesian network, is presented. The hybrid graph model has two-layers. The bottom level means user's layer and the upper one means merchandise's layer. The user's layer is an undirected arcs graph, which describes the relation of the user's nodes by small world network. The undirected arcs inside the connected nodes of user's layer mean the similarity of the preference of users. These arcs are weighted by relational strength. The weight represents node's similarity or link's strength and intensity. Nodes in the same group are more similar to each other or more strongly connected. Users in a same group have the same or similar trendy of preferences. The merchandise's layer describes the relation of goods or produce to others. It is connected by directed links, which means an implicated definition among merchandises, a user that purchase certain merchandise also tends to purchase another. The properties and content of merchandise can be used to show the similarity of the merchandise. The relations between user's layer and merchandise's layer are connected by directed links. The start node of the directed links is a user node in user's layer belonging to some node group, which is gained by small world network. The end node of links is the node of some merchandise of the merchandise's layer. The directed links between the user's layer and the merchandise's layer are connected based on trade information of users. The strength of the relation between users and merchandises can be denoted by the probability parameter. The probability parameter shows a possibility of some users selecting for some merchandises. Firstly, algorithms for users clustering and for anal- ysis of new user interest are presented to construct a hybrid graph model. Two important characteristic parameters, which are in small-world network, are introduced. These are characteristic path length and clustering coefficient. New user interest analysis is to judge which clustering group is the best match by calculating the distance of the new user node to the others user nodes. Secondly, Bayesian network for causality of merchandises and users is constructed. It can be divided two parts, structure learning and parameter learning. The paper adopts the maximal mutual information principle to restrict complexity based on degree of Bayesian network. A new maximal mutual information entropy score function with restriction is defined and a maximum likelihood estimate algorithm is used to calculated parameter. Thirdly, recommending algorithm for new user is presented. In the algorithm, the initialized inputs can utilize some users information including the attributes and browsing process of a user. A proper user-clustering group will be gained by clustering matching with other users in small world network based on this information. Then all the other users nodes, which connect to this user, are selected based on a threshold of path length in the clustering. The recommended merchandise set of these users will be obtained by Bayesian network inference using these nodes as proofs. Finally, a set of recommendation of merchandise is presented for user according to their order of probability distribution. The paper uses the mean absolute error to evaluate the model and MovieLens database is selected. The experimentation shows that the model be accomplished to represent the relationships from user to user, merchandise to merchandise, and user to merchandise. The result shows that the hybrid graph model has a good performance in personalized recommendation.     

Hierarchical Networks for Optical Communications

ShuffleNet and de Bruijn networks have been proposed as multihop lightwave networks based on wavelength division multiplexing (WDM). With multihop lightwave networks, few fixed wavelength transmitters/receivers are assigned to each user, eliminating the need for wavelength agility and pretransmission coordination. These networks have been shown to be very effective for uniform traffic. For communications with high locality, we propose two-level hierarchical networks. At the first level, each cluster of users can be connected either via a ShuffleNet (SH) or a de Bruijn network (dB). At the second level, all the clusters in the system can be connected by two rings in opposite directions (SH/Ring and dB/Ring), a de Bruijn network (dB/dB), or a ShuffleNet (SH/SH). The performance of ShuffleNet, de Bruijn networks, and the hierarchical networks SH/Ring, dB/Ring, dB/dB, and SH/SH is analyzed. For communications with a high locality, the hierarchical networks are shown to be very effective.     

移动Ad Hoc 网络安全策略研究

移动自组网是由一组带有无线收发装置的移动节点组成的无需固定设置支持的临时性的通信网络。由于移动AdHoe网络自身的脆弱性，其安全问题和安全策略正受到越来越广泛的重视。本文描述了移动AdHoe网络面临的开放链路，动态拓扑，有限资源等安全问题，并着重对应用在该网络上的安全策略进行分析研究和分类阐述。并给出一些密钥管理的改进策略。     

无线传感器网络中能量保护策略的研究

无线传感器网络是一组带有无线收发装置的传感器节点组成的临时性的网络自治系统,由于无线传感器网络的节点是用有限寿命的电池来提供的,因此能量保护策略成为该网络所有协议层的关键问题。从节点级、链路级和网络级3个层次总结和评估了适用于无线传感器网络的能量保护策略;在网络层提出了基于信道接入分簇算法的路由协议,并简述了该算法的主要实现过程;通过OPNET仿真给出相关结果。     

A Motion Planning Framework with Connectivity Management for Multiple Cooperative Robots

This paper proposes a decentralized motion planning algorithm for multiple cooperative robots subject to constraints imposed by sensors and the communication network. It consists of decentralized receding horizon planners that reside on each vehicle to navigate to individual target positions. A routing algorithm which modify the network topology based on the position of the robots and the limited range of transmitters and receivers, enables to reduce the communication link failures. A comparative study between the proposed algorithm and other existing algorithms is provided in order to show the advantages especially in terms of traveling time and communication link failure.     

Lower bounds for the mixed capacitated arc routing problem

Capacitated arc routing problems (CARP) arise in distribution or collecting problems where activities are performed by vehicles, with limited capacity, and are continuously distributed along some pre-defined links of a network. The CARP is defined either as an undirected problem or as a directed problem depending on whether the required links are undirected or directed. The mixed capacitated arc routing problem (MCARP) models a more realistic scenario since it considers directed as well as undirected required links in the associated network. We present a compact flow based model for the MCARP. Due to its large number of variables and constraints, we have created an aggregated version of the original model. Although this model is no longer valid, we show that it provides the same linear programming bound than the original model. Different sets of valid inequalities are also derived. The quality of the models is tested on benchmark instances with quite promising results.     

The Optimization Reachability Query of Large Scale Multi-Attribute Constraints Directed Graph

Today, many applications such as social network and biological network develop rapidly,the graph data will be expanded constantly on a large scale. Some classic methods can not effectively solve this scale of the graph data. In the reachability query, many technologies such as N-Hop, tree, interval labels, uncertain graph processing are emerging, they also solve a lot of questions about reachability query of graph. But, these methods have not put forward the effective solution for the new issues of the multiattribute constraints reachability on directed graph. In this paper, TCRQDG algorithm effectively solves this new problem. Firstly it optimizes the multiattribute constraints with decision making technology; secondly the algorithm achieves fast and accurate query by integrating with the Create virtual vertex expand, conditions filtering, cycles contraction, interval label and other technology. TCRQDG algorithm can not only effectively solve the new problem, but also provide technical support for multiple constraints optimization decisions of network transmission, transport and logistics, software testing and other applications.     

移动Ad Hoc网络AODV路由协议中的黑洞问题

移动自组网是由一组带有无线收发装置的移动节点组成的无须固定设置支持的临时性的通信网络。由十移动Ad Hoc网络自身的特点,其安全问题正受到越来越广泛的重视,路由在整个网络安全中扮演重要角色。该文剖析了AODV路由协议中存在的黑洞问题,在分析已有解决方案存在重大漏洞的基础上提出了一种综合的、有效的解决方案。     

自组网及其安全性研究

目前大多数的 CSCW用户只能依靠现有的网络基础设施来进行协同工作 .自组网是在 CSCW基础上为CSCW用户提供的一种通信支撑环境 ,是一组带有无线收发装置的移动节点组成的一个多跳的临时性的自治系统 .Kerberos是一个基于可信赖第三方的认证系统 ,本文在介绍自组网的同时 ,将一种改进的 Kerberos系统用于自组网体系中 ,以提高其安全性     

Accurate and efficient detection of critical links in network to minimize information loss

We address the problem of efficiently detecting critical links in a large network. Critical links are such links that their deletion exerts substantial effects on the network performance such as the average node reachability. We tackle this problem by proposing a new method which consists of three acceleration techniques: redundant-link skipping (RLS), marginal-node pruning (MNP) and burn-out following (BOF). All of them are designed to avoid unnecessary computation and work both in combination and in isolation. We tested the effectiveness of the proposed method using two real-world large networks and two synthetic large networks. In particular, we showed that the proposed method can estimate the performance degradation by link removal without introducing any approximation within a computation time comparable to that needed by the bottom-k sketch which is a summary of dataset and can efficiently process approximate queries, i.e., reachable nodes, on the original dataset, i.e., the given network. Further, we confirmed that the measures easily composed by the well known existing centralities, e.g. in/out-degree, betweenness, PageRank, authority/hub, are not able to detect critical links. Links detected by these measures do not reduce the average reachability at all, i.e., not critical at all.     

一种基于AODV的MANET入侵识别协议

入侵识别在移动Ad hoc网络路由安全中起到重要作用。该文针对AODV协议中的虚假目的序列号攻击以及已有解决方案中的缺陷,引入信誉值更新算法,设计一种基于AODV的入侵识别协议。仿真实验结果表明,该协议在网络性能以及识别的准确性方面都有较好的表现。     

On detection performance and system configuration of MIMO radar

Multiple-input multiple-output (MIMO) radar is a new concept with some new characteristics, such as multiple orthogonal waveforms and omnidirectional coverage. Based on Stein’s lemma, we use relative entropy as a precise and general measure of error exponent to study detection performance for both MIMO radar and phased array radar. And based on derived analytical results, we further study the system configuration problem of Bistatic MIMO radar systems, where transmitters and receivers are located in different positions. Some interesting results are presented. For phased array radar, when the total numbers of transmitters and receivers are fixed, we should alwaysmake the number of transmitters equal to the number of receivers. For MIMO radar, we should use a small number of transmitters in low signal noise ratio (SNR) region, and make the number of transmitters equal to the number of receivers in high SNR region. These results are instructive for deployment of bistatic MIMO radar systems in the future. Supported in part by the National Natural Science Foundation of China (Grant No. 60602048), in part by aviation science funds of China (Grant No. 20060112118), and in part by the National Ministry Foundation of China (Grant No. 20094010040)     

Distributed Fair Resource Allocation in Cellular Networks in the Presence of Heterogeneous Delays

We consider the problem of allocating resources at a base station to many competing flows, where each flow is intended for a different receiver. The channel conditions may be time-varying and different for different receivers. It has been shown in a previous paper that in a delay-free network, a combination of queue-length-based scheduling at the base station and congestion control at the end users can guarantee queue-length stability and fair resource allocation. In this note, we extend this result to wireless networks where the congestion information from the base station is received with a feedback delay at the transmitters