认知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网络一般有平面结构和分级结构两种结构，在网络中的节点数比较事的情况下需要使用分级结构．本文主要介绍四种簇形成算法及其优缺点和适用场合。     

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

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

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

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

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

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

Ad Hoc网络基于簇的多信道MAC协议研究

介绍了一种适用于Ad Hoc网络的基于簇的多信道媒体接入控制协议。在该协议中,整个网络被划分成使用不同频道的若干个簇,每个节点配置有3个独立的无线收发信机,由簇首节点负责簇的维持功能,由簇首和簇成员节点通过共同执行信道重配置算法来完成信道分配工作。仿真结果表明,该协议可以很好地适应网络拓扑结构的频繁变化,在充分利用多信道优势工作的同时,解决了普遍存在于多跳无线移动网络中的隐藏终端和暴露终端问题。     

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     

Reliability evaluation for distributed computing networks withimperfect nodes

This paper examines two compensating methods that: (1) account for imperfect nodes, and (2) can be embedded in most symbolic network reliability algorithms that presume perfect nodes. The Aggarwal method can be exponential in time with the number of links, whereas the Torrieri method is always linear. However the Torrieri method can yield incorrect results for some undirected networks. This paper points out such incorrectness and then proposes an efficient reliability evaluation algorithm (ENR/KW) accounting for imperfect nodes in distributed computing networks. Based on the concept of network partition, ENR/KW exploits some simple efficient techniques to handle the unreliable nodes, for directly computing the network reliability expression considering imperfect nodes instead of using any compensating method. The basic idea of ENR/KW is to partition the network directly into a set of smaller disjoint subnetworks by only considering link elements as if all nodes are perfect. Each disjoint subnetwork is generated by maintaining a specific directed graph structure to consider the effect of imperfect nodes. Therefore, the reliability expression for imperfect nodes can be obtained directly from the disjoint subnetwork and the specific directed graph. ENR/KW can be generalized to evaluate various network reliability measures considering imperfect nodes such as terminal-pair reliability, K-terminal reliability, and distributed-program reliability. Many experiments for evaluating the terminal-pair reliability and distributed-program reliability were performed on a SUN workstation to show the efficiency of ENR/KW in terms of the number of generated subnetworks and overall computation time