Finding the most vital edges with respect to the number of spanningtrees

A most vital edge of a graph (w.r.t. the spanning trees) is an edge whose deletion most drastically decreases the number of spanning trees. We present an algorithm for determining the most vital edges based on Kirchoff's matrix-tree theorem whose asymptotic time-complexity can be reduced to that of the fastest matrix multiplication routine, currently O(n^2.376). The foundation for this approach is a more general algorithm for directed graphs for counting the rooted spanning arborescences containing each of the arcs of a digraph. A network can be modeled as a probabilistic graph. Under one such model proposed by Kel'mans, the all-terminal network reliability, maximizing the number of spanning trees is critical to maximizing reliability when edges are very unreliable. For this model, the most vital edges characterize the locations where an improvement of the reliability of the link most improves the reliability of the network     

基于网络编码的双路径组播树生成算法

 为了将网络编码技术引入到全光组播网络中,提出了能够在多项式时间完成的基于网络编码的双路径组播树生成算法.该算法主要包括两大步骤:首先,从给定的组播网络中根据节点间度平衡的原则为源节点和每个目的节点之间确定一条有向路径,从而建立一棵传统有向树并保证有向树中任意节点的出度尽可能小,减少节点之间的关联性;其次,在所建立的传统有向树的基础上,从每一个目的节点到源节点根据冲突回溯原则建立源节点和每个目的节点之间的第二条路径,并保证源节点到任意目的节点间的两条路径为分离路径.算法中包含的约束原则能够保证所建立的双路径组播树包含最少的编码节点,从而使得所建立的组播树支持光域网络编码高效率实现,实现基于网络编码的全光组播并提升全光组播的性能.     

Mobility prediction in mobile ad hoc networks using a lightweight genetic algorithm

A mobile ad hoc network is a collection of wireless mobile nodes creating a network without using any existing infrastructure. Much research has been carried out to find out an optimal routing protocol for the successful transmission of data in this network. The main hindrance is the mobility of the network. If the mobility pattern of the network can be predicted, it will help in improving the QoS of the network. This paper discusses a novel approach to mobility prediction using movement history and existing concepts of genetic algorithms, to improve the MANET routing algorithms. The proposed lightweight genetic algorithm performs outlier removal on the basis of heuristics and parent selection using the weighted roulette wheel algorithm. After performing the genetic operations a node to node adjacency matrix is obtained from which the predicted direction of each node is calculated using force directed graphs and vector calculations. The technique proposes a new approach to mobility prediction which does not depend on probabilistic methods and which is completely based on genetic algorithms.     

网树求解有向无环图中具有长度约束的最大不相交路径

对有向无环图中具有长度约束的最大不相交路径问题进行研究,该问题是求解图中两点间路径长度为k的最大不相交路径。为了对该问题进行求解,提出了贪婪搜索算法(GP, greedy path),该算法先将一个有向无环图转化为一棵深度为k+1的网树,然后计算每个网树节点的树根叶子路径数,并以此计算图中每个顶点的总路径数,之后从网树的第k+1层节点出发,在当前节点的双亲节点中选择未被使用且总路径数最小的双亲,以此形成一条优化的不相交路径,最后迭代这一过程,直到不再有新的不相交路径为止。GP算法的时间和空间复杂度分别为O(wkn(p+q))和O(kn(p+q)+n2)。为了测试GP算法的近似性,又建立了一种能够生成人工数据的算法,该算法能够准确地控制有向无环图中最大不相交路径的数量。通过该算法生成了大量测试用数据,实验结果表明GP算法较其他对比性算法具有良好的近似性且实际求解时间较短,验证了该方法的有效性和可行性。     

Bottleneck multicast trees in linear time

On a directed graph with arc costs and a given source node, s, we consider the problem of computing multicast (Steiner) trees spanning any given node subset, V, so that the maximum of the tree arc costs is minimized. We show that this problem can be solved by simply solving the bottleneck path problem, i.e., the problem of determining for each node, t/spl ne/s, a path from s to t so that the maximum of path arc costs is minimized. For the latter problem we provide an implementation of Dijkstra's algorithm that runs in linear time under mild assumptions on arc costs.     

A Recursive Algorithm For Bounding Network Reliability

This paper presents a new recursive algorithm for computing bounds on the reliability of a directed, source-sink network whose arcs either function or fail with known probabilities. The reliability is the probability that a path (consisting only of functioning arcs) exists from the network's source to its sink. The algorithm is based on a partitioning of the nodes of the network into subsets S1, S2,..., SP such that all predecessors of a node belonging to Sp(2)相似文献   

Power and cost aware localized routing with guaranteed delivery in unit graph based ad hoc networks

In a localized routing algorithm, each node currently holding a message makes forwarding decision solely based on the position information about itself, its neighbors and destination. In a unit graph, two nodes can communicate if and only if the distance between them is no more than the transmission radius, which is the same for each node. This paper proposes localized routing algorithms, aimed at minimizing total power for routing a message or maximizing the total number of routing tasks that a network can perform before a partition. The algorithms are combinations of known greedy power and/or cost aware localized routing algorithms and an algorithm that guarantees delivery. A shortcut procedure is introduced in later algorithm to enhance its performance. Another improvement is to restrict the routing to nodes in a dominating set. These improvements require two‐hop knowledge at each node. The efficiency of proposed algorithms is verified experimentally by comparing their power savings, and the number of routing tasks a network can perform before a node loses all its energy, with the corresponding shortest weighted path algorithms and localized algorithms that use fixed transmission power at each node. Significant energy savings are obtained, and feasibility of applying power and cost‐aware localized schemes is demonstrated. Copyright © 2004 John Wiley & Sons, Ltd.     

基于Gossip算法的定向扩散协议研究

通过对现有定向扩散协议的研究,考虑到无线传感器网络对于各节点的能量和整个网络的开销的要求,提出将逾渗算法应用于定向扩散协议的兴趣扩散阶段。定向扩散协议的兴趣扩散是以广播的形式发送数据,而逾渗算法的加入是使各个节点以一定的概率p（P〈1）发送数据给邻居节点,只要这个概率值大于或等于整个网络连通的临界值,就能保证这个网络中的各个节点都能顺利地接收到信息,并同时达到减少网络开销的目的。     

Distributed algorithms for computing shortest pairs of disjointpaths

Distributed algorithms for finding two disjoint paths of minimum total length from each node to a destination are presented. The algorithms have both node-disjoint and link-disjoint versions and provide each node with information sufficient to forward data on the disjoint paths. It is shown that this problem can be reduced to the problem of finding a minimal shortest path from each node to the destination in a modified network, and a distributed algorithm on the original network that simulates a shortest-paths algorithm running on the modified network is presented. The algorithm has a smaller space complexity than any previous distributed algorithm for the same problem, and a method for forwarding packets is presented that does not require any additional space complexity. A synchronous implementation of the algorithm is also presented and studied     

Nature inspired discrete firefly algorithm for optimal mobile data gathering in wireless sensor networks

Nowadays wireless sensor networks enhance the life of human beings by helping them through several applications like precision agriculture, health monitoring, landslide detection, pollution control, etc. The built-in sensors on a sensor node are used to measure the various events like temperature, vibration, gas emission, etc., in the remotely deployed unmanned environment. The limited energy constraint of the sensor node causes a huge impact on the lifetime of the deployed network. The data transmitted by each sensor node cause significant energy consumption and it has to be efficiently used to improve the lifetime of the network. The energy consumption can be reduced significantly by incorporating mobility on a sink node. Thus the mobile data gathering can result in reduced energy consumption among all sensor nodes while transmitting their data. A special mobile sink node named as the mobile data transporter (MDT) is introduced in this paper to collect the information from the sensor nodes by visiting each of them and finally it sends them to the base station. The Data collection by the MDT is formulated as a discrete optimization problem which is termed as a data gathering tour problem. To reduce the distance traveled by the MDT during its tour, a nature-inspired heuristic discrete firefly algorithm is proposed in this paper to optimally collect the data from the sensor nodes. The proposed algorithm computes an optimal order to visit the sensor nodes by the MDT to collect their data with minimal travel distance. The proposed algorithm is compared with tree-based data collection approaches and ant colony optimization approach. The results demonstrate that the proposed algorithm outperform other approaches minimizing the tour length under different scenarios.     

基于分布式软件无线电的微波能量传输方法

设计了一种基于软件无线电、节点相对独立、分布式波束形成的微波能量无线传输方法。采用扩展 卡尔曼滤波算法估计和校正每个发射节点发射信号的载波频率偏移,并采用一比特反馈算法调整每个发射节点的 发射相位,以此将它们的能量集中在接收节点,使收集能量最大化从而提高输能效率。实验结果表明:采用所设计 的方法在四个发送节点的情况下,接收节点可以获得11. 54 dB 的增益,可以大幅提高微波输能效率,为进一步展开 微波能量为低功耗电子设备无线充电奠定基础。     

基于移动预测模型的ad hoc网络稳定链路度量

提出了一种基于移动预测模型的稳定链路度量算法，定义了稳定邻居度量和本地运动度量2种测度。根据这2种测度，移动预测模型利用LZ78算法对本地节点与其邻居的稳定性概率进行预测，从而找到其最稳定邻居，为选择稳定路由提供依据。仿真结果表明此算法明显优于直方图算法及最小ID算法，所选链路的稳定性能显著提高。     

基于进化规划的多层前向网络结构优化

基于进化规划(EP)方法,该文提出了设计多层前向网络拓扑结构和权值分布的一种新算法EPANN算法。EPANN算法能同时进化网络的结构和连接权值(包括阈值),在进化过程中,强调父代和子代之间的行为联结,结构变异既有结点删除,又有结点增加,不同于单纯的删除算法或构造算法,且结点删除总是先于结点增加,保证了网络规模尽可能小而泛化能力尽可能强。     

Ternary Schedules for Energy-Limited Sensor Networks

Medium access control for multihop wireless sensor networks (WSNs) must be energy efficient because the battery-operated nodes are not practical to recharge. We give constructions for ternary schedules in which each node is in one of three states: transmitting, receiving, or asleep. For each hop (v_i, v_j), communication is effective only when v_i is transmitting, v_j is receiving, and no other node in proximity of v_j is also transmitting. Since sensor nodes are prone to failure, the schedules should be independent of the detailed topology while supporting spatial reuse. We use arc-decompositions of the complete lambda-fold directed graph Koarr_n into directed complete bipartite subgraphs Koarr_a,b as a model for ternary scheduling in WSNs. We associate the vertices of Koarr_n with the nodes of the WSN, and occurrences of Koarr_a,bs (blocks) in the decomposition with time slots in the schedule. A block with out-vertices A and in-vertices B corresponds to a slot in which the a nodes in A are transmitting, the b in B are receiving, and all others are asleep. Such a decomposition of lambdaKoarr_nguarantees that every ordered pair of nodes in the WSN can communicate in lambda time slots.     

An efficient heuristic force directed placement algorithm based on partitioning

An efficient heuristic force directed placement algorithm based on partitioning is proposed for very large-scale circuits. Our heuristic force directed approach provides a more efficient cell location adjustment scheme for iterative placement optimization than the force directed relaxation (FDR) method. We apply hierarchical partitioning based on a new parallel clustering technique to decompose circuit into several level sub-circuits. During the partitioning phase, a similar technique to ‘terminal propagation’ was introduced so as to maintain the external connections that affect cell adjustment in sub-circuit. In these lowest level sub-circuits, the heuristic force directed algorithm is used to perform iterative placement optimization. Then each pair of sub-circuits resulted from bisection combine into a larger one, in which cells are located as the best placement state of either sub-circuits. The bottom-up combination is done successively until back to the original circuit, and at each combination level the heuristic force directed placement algorithm is used to further improve the placement quality. A set of MCNC (Microelectronics Centre of North-Carolina) standard cell benchmarks is experimented and results show that our placement algorithm produces on average of 12% lower total wire length than that of Feng Shui with a little longer CPU time.     

基于中断概率的多跳混合协作地理路由算法

为了减小无线传感器网络中路由的路径长度,该文提出基于中断概率的多跳混合协作地理路由(MHCGR)算法。首先对不同协作机制的链路进行分析,理论分析表明,在一定中断概率要求下,采用译码放大转发混合协作机制可以进一步扩大传输距离,并推导了每跳协作链路的理想最大协作传输距离和理想中继的位置。在无信标地理路由(BLGR)算法的基础上,MHCGR算法结合节点位置信息为每跳选择最佳的中继节点和转发节点,建立从源节点到目的节点的多跳协作路由。仿真表明,与ENBGCR算法和基于DF协作机制的MPCR算法两种协作地理路由算法相比,MHCGR算法可明显减少路由的跳数,改善路由的整体发射功率。     

Finding parity in a simple broadcast network

A broadcast network of N+1 nodes is considered in which each binary digit transmitted by each node is received by every other node via a binary symmetric channel of given transition probability. The errors on these channels are independent over transmitters, receivers and time. Each node has a binary state, and the problem is to construct a distributed algorithm to find the parity of the set of states with some given reliability. It is shown that this can be done with O(ln(ln N)) bits of communication from each node. Communicating all the node states to one node can be accomplished with only marginally more communication     

Link optimization strategy based on spectral moment in wireless sensor network

In order to prolong the life of the wireless sensor network (WSN),an adaptive local communication link optimization algorithm of nodes was proposed to optimize the network structure dynamically.By introducing the term of Laplacian spectrum moment,each node can make the decision of adding or deleting a link iteratively with their neighborsusinglimited local network structural information,and then the whole network can evolve to a predefined structure.The experimental results show that each node takes only finite iterations and then the network structure can converge quickly to the target,which prove the effectiveness of the algorithm.     

Deadlock Avoidance in Store-and-Forward Networks--I: Store-and-Forward Deadlock

Store-and-forward deadlock in store-and-forward networks may be avoided by forwarding messages from buffer to buffer in accordance with a loop-free directed buffer graph which accommodates all the desired message routes. Schemes for designing such buffer graphs are presented, together with methods for using them to forward the messages in an efficient and deadlock-free manner. These methods can be implemented by a set of counters at each node. Such an implementation increases the efficiency of buffer use, and simplifies jumping between normal lowoverhead operation when deadlock is far and more careful operation when deadlock is near. The proposed deadlock avoidance mechanism works for any network topology and any finite routing algorithm.     

Key nodes of the trust transitivity in social Internet of things

The trustee and the trustor may have no previous interaction experiences before. So, intermediate nodes which are trusted by both the trustor and the trustee are selected to transit trust between them. But only a few intermediate nodes are key nodes which can significantly affect the transitivity of trust. To the best of our knowledge, there are no algorithms for finding key nodes of the trust transitivity. To solve this problem, the concept of trust is presented, and a comprehensive model of the transitivity of trust is provided. Then, the key nodes search (KNS) algorithm is proposed to find out the key nodes of the trust transitivity. The KNS algorithm is verified with three real social network datasets and the results show that the algorithm can find out all the key nodes for each node in directed, weighted, and non-fully connected social Internet of things (SIoT) networks.