认知Ad Hoc网络中基于信道相似度的分簇算法研究

针对传统分簇算法无法适用于信道动态变化的认知Ad Hoc网络,提出了一种基于信道相似度的分布式分簇算法.首先计算节点间的信道相似度,利用改进的EM算法估计节点属于不同簇的概率,再结合图的最小割算法取得最优的分簇结果.算法既最大化簇内相似度,也最小化簇间相似度.最后,提出了一个协调机制,可以同步全局的分簇信息.整个过程完全分布式运行,并且无需依赖公共控制信道.仿真结果表明,算法能够根据信道变化,动态地调整分簇结构,提高簇内公共信道数量.与此同时,算法还能有效减少簇间公共信道,降低簇间通信干扰.     

无线Ad hoc网络路由协议比较

无线Ad hoe网络是一种新型的移动计算网络,本文首先介绍了Ad hoe网络的特点以及路由协议分类,然后针对四种典型的路由协议通过NS2仿真器进行了仿真分析和性能比较,并得出了结论。     

网络系统可靠度的BDD算法

文中研究3-状态设备网络系统2-终端可靠度的计算问题。BDD是布尔函数的图形表示形式。武小悦和沙基昌提出了一个采用BDD方法求2-状态网络系统的不交化最小路集,从而直接计算网络系统可靠度的算法。通过引入简化技术,结合归约公式和BDD技术,给出了一个计算3-状态设备网络2-终端可靠度的一个新算法;算法有效地消除了冗余项,并且产生的分枝树具有结点少,可有效得到可靠度符号表达式。     

一个基于层次结构的Ad hoc网络移动模式

采用连通图中极小支配集概念对平面分布的Ad hoc网络进行层次划分；提出移动节点之间的相关度概念，利用GM-BFS算法来实现Ad hoc网络的簇结构生成。结果显示提出的分簇模式能较好地适应网络的扩展、簇生成算法具有收敛快的特征。     

基于随机时变图的时间确定性网络路由算法

针对天地一体化网络环境中网络时变性和业务时延确定性保障之间的矛盾,构建了随机时变图模型,并基于该模型提出了时间确定性网络路由算法.首先,将空间信息网络最大概率时延保障路由计算问题建模为非线性规划问题.为解决该问题,提出了随机时变图模型,联合表征了由业务随机性导致的链路、存储与时间资源的随机特征,并且表征了存储与链路资源...     

VANET中基于线性协作策略的预警信息检测算法

提出了一种车载Ad Hoc网络中基于线性协作策略的交通事故预警信息检测算法,由两个部分组成:局部检测和全局检测。簇首得到移动车辆节点局部检测后的信号强度统计量,进行全局线性组合,做出最终的判决。数值仿真结果表明所提出的策略能在误警概率要求范围内有效提高检测概率,并且避免广播风暴的发生。     

分级Ad Hoc网络簇形成算法的比较

Ad hoc网络是由若干移动节点组成的无中心网络，它在尚没有架设基础通信设施的地区及一些紧急情况下的通信将有广泛的用途。Ad Hoc网络一般有平面结构和分级结构两种结构，在网络中的节点数比较事的情况下需要使用分级结构．本文主要介绍四种簇形成算法及其优缺点和适用场合。     

高可靠光纤布拉格光栅传感器网络设计

对采用光纤布拉格光栅(FBG)传感器网络监测某飞机机翼盒段外加载荷位置信息进行了研究。研究了FBG传感器网络中传感器失效对外加载荷位置识别精度的影响程度;针对传统FBG传感器网络拓扑结构可靠性低的缺点,引入光开关,设计了一种具有更高可靠性的传感器网络拓扑结构,并对这两种网络结构的可靠性进行了研究。结果表明,新传感器网络的可靠性明显高于传统传感器网络的可靠性。单个传感器的失效概率不同,两种传感器网络可靠性差别也不同;当单个元器件的失效概率在0.001~0.01之间变动时,若系统允许外加载荷位置识别误差在5 mm内,则新传感器网络的失效率降为传统网络失效率的50%;若系统允许外加载荷位置识别误差在10 mm内,则新传感器网络的失效率至少降低为传统网络失效率的12.5%。     

无线Ad Hoc网络中基于活跃节点数预测的时隙ALOHA算法

针对采用时隙ALOHA算法的无线Ad Hoc网络,考虑数据包到达的动态性与数据包传输的随机性,以最大化吞吐量为目标,同时满足数据队列稳定性,构建了关于接纳控制与竞争接入的随机优化问题。由于在时隙ALOHA算法中数据包传输的最优概率取决于无线Ad Hoc网络中数据队列非空的活跃节点数,提出了一种基于活跃节点数预测的时隙ALOHA算法。该算法要求无线Ad Hoc网络中的所有发送节点实时地侦听通信信道的忙闲状态,计算基于信道状态的活跃节点数条件期望,从而动态地预测无线Ad Hoc网络在不同时刻的活跃节点数,达到网络节点依据局部网络状态信息自适应地优化数据包传输概率的目的。仿真结果表明,所提算法能够有效估计无线Ad Hoc网络在每个时隙的活跃节点数,从而显著提升网络吞吐量并且降低数据包的平均排队时延。     

基于改进蚁群算法的Ad hoc路由协议的研究

现有Ad hoc网络路由协议技术研究中,路由稳定性和可靠性问题尚未得到很好解决,不能很好地适应Adhoc网络.针对已有Ad hoc路由技术中存在的开销大以及网络稳定性较低的问题,该文引入蚁群算法,并对其进行改进.研究基于改进蚂蚁算法的Ad hoc路由协议,并与比较成熟的AODV(Ad hoc On-Demand Distance Vector)进行对比.仿真实验结果表明,通过发挥网络中结点群体功能,新协议减小了端对端传输延时,改善了数据包传输成功率与协议开销,有效地提高了网络的稳定性和通信效率.     

A linear-time algorithm for computing K-terminal reliability onproper interval graphs

Consider a probabilistic graph in which the edges are perfectly reliable, but vertices can fail with some known probabilities. The K-terminal reliability of this graph is the probability that a given set of vertices K is connected. This reliability problem is #P-complete for general graphs, and remains #P-complete for chordal graphs and comparability graphs. This paper presents a linear-time algorithm for computing K-terminal reliability on proper interval graphs. A graph G = (V, E) is a proper interval graph if there exists a mapping from V to a class of intervals I of the real line with the properties that two vertices in G are adjacent if their corresponding intervals overlap and no interval in I properly contains another. This algorithm can be implemented in O(|V| + |E|) time     

无线广播网络的可靠性分析

本文提出了一个计算无线广播网络的Ｋ－终点可靠度方法。因为ＲＢＮ的Ｋ－终点可靠度问题是个ＮＰ－困难问题,所以已有的结果只是一些近似算法和针对某些特殊ＲＢＮ的算法。     

Factoring Algorithms for Computing K-Terminal Network Reliability

Let GK denote a graph G whose edges can fail and with a set K ? V specified. Edge failures are independent and have known probabilities. The K-terminal reliability of GK, R(GK), is the probability that all vertices in K are connected by working edges. A factoring algorithm for computing network reliability recursively applies the formula R(GK) = piR(GK * ei) + qiR(GK - ei) where GK * ei is GK, with edge ei contracted, GK - ei is GK with ei deleted and pi ? 1 - qi is the reliability of edge ei. Various reliability-preserving reductions can be performed after each factoring operation in order to reduce computation. A unified framework is provided for complexity analysis and for determining optimal factoring strategies. Recent results are reviewed and extended within this framework.     

A unified domination approach for reliability analysis of networkswith arbitrary logic in vertices

The concept of a probabilistic graph G has been used as a universal model for network reliability. Most of the literature on this subject concentrates on computing various reliability measures (such as k-terminal reliability or all-terminal reliability) which are the probability that vertices of G can communicate with other specified vertices. Primarily, this paper provides a common theoretical framework for addressing k-terminal reliability problems. To this end, it extends the model admitting vertex functions of G to be arbitrary monotone Boolean functions: in this case G is called a monotone (S,t)-graph. In such graphs the signal passability across a node is carried out in accordance with collections of signals delivered on the node inputs from other ones, the collections are subjected to some logic principle realized by a Boolean function. Monotone (S,t)-graphs include all known classes of directed multi-terminal network reliability models. The main result of this paper is the reliability expression for computing the probability of an acyclic monotone (S,t)-graph G being operational. The expression uses the local domination parameters introduced here. That reduces the system level of consideration to the element level, providing a unifying understanding of the combinatorial nature of some results based on the domination theory and developed earlier for ordinary networks     

A linear-time algorithm to compute the reliability of planarcube-free networks

A planar graph G=(V,E) is a cube-free graph (CF graph) if it has no subgraph homomorphic to the cube. The cube is the graph whose vertices and edges are the vertices and edges of the three dimensional geometric cube. The all-terminal reliability of a graph G whose edges can fail (with known probabilities) is the probability that G is connected. The problem of computing the all-terminal reliability of a general graph is NP-hard. An O(| V|) time algorithm for computing the all-terminal reliability of CF graphs is presented     

K-Terminal Network Reliability Measures With Binary Decision Diagrams

We present a network decomposition method using binary decision diagrams (BDD), a state-of-the-art data structure to encode, and manipulate Boolean functions, for computing the reliability of networks such as computer, communication, or power networks. We consider the K-terminal reliability measure R_K, which is defined as the probability that a subset K of nodes can communicate with each other, taking into account the possible failures of the network links. We present an exact algorithm for computing the if-terminal reliability of a network with perfect vertices in O(m^.F_max ^.2^Fmax.B_Fmax), where B_Fmax is the Bell number of the maximum boundary set of vertices F_max, and m is the number of network links. Several examples, and experiments show the effectiveness of this approach.     

A New Algorithm for the Reliability Analysis of Multi-Terminal Networks

In a probabilistic network, source-to-multiple-terminal reliability (SMT reliability) is the probability that a specified vertex can reach every other vertex. This paper derives a new topological formula for the SMT reliability of probabilistic networks. The formula generates only non-cancelling terms. The non-cancelling terms in the reliability expression correspond one-to-one with the acyclic t-subgraphs of the network. An acyclic t-subgraph is an acyclic graph in which every link is in at least one spanning rooted tree of the graph. The sign to be associated with each term is easily computed by counting the vertices and links in the corresponding subgraph. Overall reliability is the probability that every vertex can reach every other vertex in the network. For an undirected network, it is shown the SMT reliability is equal to the overall reliability. The formula is general and applies to networks containing directed or undirected links. Furthermore link failures in the network can be s-dependent. An algorithm is presented for generating all acyclic t-subgraphs and computing the reliability of the network. The reliability expression is obtained in symbolic factored form.     

求二部图的最大匹配图的一种算法

 一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对Gallai Edmonds结构定理中的三部分顶点在二部图中进行了详细刻画.然后讨论了构造最大匹配图问题的计算复杂性.最后深入研究了二部图最大匹配图的结构性质并给出了构造二部图的最大匹配图的一种算法.     

K-terminal reliability in ring networks

The authors present a new formula for computing K-terminal reliability in a communication network whose stations and links (vertices and edges) form a network graph G having a ring topology, where K-terminal reliability is the probability R_K(G) that a subset of R specific terminal stations in G can communicate. This new formula is applied to three Fiber Distributed Data Interface (FDDI) ring-network topologies, and for each topology the authors derive closed-form polynomial expressions of R_K(G) in terms of the failure probabilities of links, network ports, and station common units. The authors define the concept of the K-minimal Eulerian circuit and use combinations of these circuits to obtain K-graphs and their resulting dominations, thus extending the use of K-graphs to ring networks in which data messages, tokens, or other control frames traverse operative network links with an Eulerian tour. Distinct K-graphs having a nonzero sum of dominations are called noncanceled K-graphs and correspond exactly to terms in closed-form polynomial expressions of R_K(G). The authors show that trees have only one K-graph and that counter-rotating dual rings and rings of trees have at most 2K+1 noncanceled R-graphs. These results contribute the first closed-form polynomial R-terminal reliability expressions for the ring-of-trees topology. The results are useful in evaluating dependability, reliability, availability, or survivability of token rings and similar networks     

基于扩散算子的带限图信号加权重建策略

图信号处理技术将经典信号处理的概念和算法延展到图结构信号的处理领域。对于带限图信号,可以通过分析信号之间的关联性,重建出未采样的信号。该文分析了未采样信号的构成架构,提出一个基于扩散算子的未采样信号迭代重建算法。在每次迭代过程中,将已采样信号的重建残差扩散至所有未采样的信号节点,并进一步通过初步估计结果与重建残差的加权处理,提升算法的收敛速度。采用合成数据和真实数据进行仿真验证,实验结果显示所提出的算法具有低重建误差和快速收敛的特点。