Core-based Shared Tree Multicast Routing Algorithms for LEO Satellite IP Networks

A new core-based shared tree algorithm, viz core-cluster combination-based shared tree （CCST） algorithm and the weighted version （i.e. w-CCST algorithm） are proposed in order to resolve the channel resources waste problem in typical source-based multicast routing algorithms in low earth orbit （LEO） satellite IP networks. The CCST algorithm includes the dynamic approximate center （DAC） core selection method and the core-cluster combination multicast route construction scheme. Without complicated onboard computation, the DAC method is uniquely developed for highly dynamic networks of periodical and regular movement. The core-cluster combination method takes core node as the initial core-cluster, and expands it stepwise to construct an entire multicast tree at the lowest tree cost by a shortest path scheme between the newly-generated core-cluster and surplus group members, which results in great bandwidth utilization. Moreover, the w-CCST algorithm is able to strike a balance between performance of tree cost and that of end-to-end propagation delay by adjusting the weighted factor to meet strict end-to-end delay requirements of some real-time multicast services at the expense of a slight increase in tree cost. Finally, performance comparison is conducted between the proposed algorithms and typical algorithms in LEO satellite IP networks. Simulation results show that the CCST algorithm significantly decreases the average tree cost against to the others, and also the average end-to-end propagation delay ofw-CCST algorithm is lower than that of the CCST algorithm.

Simulating Transport Capacity, Delivery Speed, and Routing Efficiency to Predict Economic Growth

This study uses a simulation-based approach to investigate the impact of delivery delays due to constraints on transport capacity, transit speed, and routing efficiencies on an economy with various levels of interdependency among firms. The simulation uses object-oriented programming to create specialized production, consumption, and transportation classes. A set of objects from each class is distributed randomly on a 2D plane. A road network is then established between fixed objects using Prim’s MST (Minimum Spanning Tree) algorithm, followed by construction of an all-pair shortest path matrix using the Floyd Warshall algorithm. A genetic algorithm-based vehicle routing problem solver employs the all-pair shortest path matrix to best plan multiple pickup and delivery orders. Production units utilize economic order quantities (EOQ) and reorder points (ROP) to manage inventory levels. Hicksian and Marshallian demand functions are utilized by consumption units to maximize personal utility. The transport capacity, transit speed, routing efficiency, and level of interdependence serve as 4 factors in the simulation, each assigned 3 distinct levels. Federov’s exchange algorithm is used to generate an orthogonal array to reduce the number of combination replays from 34 to just 9. The simulation results of a 9-run orthogonal array on an economy with 6 mining facilities, 12 industries, 8 market centers, and 8 transport hubs show that the level of firm interdependence, followed by transit speed, has the most significant impact on economic productivity. The principal component analysis (PCA) indicates that interdependence and transit speed can explain 90.27% of the variance in the data. According to the findings of this research, a dependable and efficient regional transportation network among various types of industries is critical for regional economic development.

A Study on Priority Based ZigBee Network Performance Analysis with Tree Routing Method

The Wireless Sensor Network (WSN) is spatially distributed autonomous sensor to sense special task. WSN like ZigBee network forms simple interconnecting, low power, and low processing capability wireless devices. The ZigBee devices facilitate numerous applications such as pervasive computing, security monitoring and control. ZigBee end devices collect sensing data and send them to ZigBee Coordinator. The Coordinator processes end device requests. The effect of a large number of random unsynchronized requests may degrade the overall network performance. An effective technique is particularly needed for synchronizing available node’s request processing to design a reliable ZigBee network. In this paper, region based priority mechanism is implemented to synchronize request with Tree Routing Method. Riverbed is used to simulate and analyze overall ZigBee network performance. The results show that the performance of the overall priority based ZigBee network model is better than without a priority based model. This research paves the way for further designing and modeling a large scale ZigBee network.

Tree Based Energy and Congestion Aware Routing Protocol for Wireless Sensor Networks

Wireless Sensor Networks (WSNs) have inherent and unique characteristics rather than traditional networks. They have many different constraints, such as computational power, storage capacity, energy supply and etc;of course the most important issue is their energy constraint. Energy aware routing protocol is very important in WSN, but routing protocol which only considers energy has not efficient performance. Therefore considering other parameters beside energy efficiency is crucial for protocols efficiency. Depending on sensor network application, different parameters can be considered for its protocols. Congestion management can affect routing protocol performance. Congestion occurrence in network nodes leads to increasing packet loss and energy consumption. Another parameter which affects routing protocol efficiency is providing fairness in nodes energy consumption. When fairness is not considered in routing process, network will be partitioned very soon and then the network performance will be decreased. In this paper a Tree based Energy and Congestion Aware Routing Protocol (TECARP) is proposed. The proposed protocol is an energy efficient routing protocol which tries to manage congestion and to provide fairness in network. Simulation results shown in this paper imply that the TECARP has achieved its goals.

Tree-Based Proactive Routing Protocol for Wireless Mesh Network

Wireless Mesh Network (WMN) is seen as an effective Internet access solution for dynamic wireless applications. For the low mobility of mesh routers in WMN, the backbone topography can be effectively maintained by proactive routing protocol. Pre-proposals like Tree Based Routing (TBR) protocol and Root Driven Routing (RDR) protocol are so centralized that they make the gateway become a bottleneck which severely restricts the network performance. We proposed an Optimized Tree-based Routing (OTR) protocol that logically separated the proactive tree into pieces. Route is partly computed by the branches instead of root. We also discussed the operation of multiple Internet gateways which is a main issue in WMN. The new proposal lightens the load in root, reduces the overhead and improves the throughput. Numerical analysis and simulation results confirm that the performance of WMN is improved and OTR is more suitable for large scale WMN.

Constructing Multicast Routing Tree for Inter-cloud Data Transmission：An Approximation Algorithmic Perspective

Networking plays a crucial role in cloud computing especially in an inter-cloud environment, where data communications among data centers located at different geographical sites form the foundation of inter-cloud federation. Data transmissions required for inter-cloud federation in the complex inter-cloud networking system are often point-to-multi points, which calls for a more effective and efficient multicast routing algorithm in complex networking systems. In this paper, we investigate the multicast routing problem in the inter-cloud context with K constraints where K ≥ 2. Unlike most of existing algorithms that are too complex to be applied in practical scenarios, a novel and fast algorithm for establishing multicast routing tree for interclouds is proposed. The proposed algorithm leverages an entropybased process to aggregate all weights into a comprehensive metric, and then uses it to search a multicast tree(MT) on the basis of the shortest path tree(SPT). We conduct complexity analysis and extensive simulations for the proposed algorithm from the approximation perspective. Both analytical and experimental results demonstrate that the algorithm is more efficient than a representative multi-constrained multicast routing algorithm in terms of both speed and accuracy, and thus we believe that the proposed algorithm is applicable to the inter-cloud environment.

An Efficient Routing Tree Algorithm for Combined Uplink and Downlink Subframes on Centralized Scheduling in IEEE 802.16 Based Wireless Mesh Networks

IEEE 802.16 mesh mode defines routing tree for transmitting data in centralized scheduling but it does not define any explicit proposal for combining uplink and downlink subframes. Deploying combined uplink and downlink subframes on the centralized scheduling scheme can be more flexible and utilization is improved. However, existing interferences among the transmission of neighboring nodes lead to performance reduction of the network. In this paper, an efficient routing tree algorithm is proposed with combined uplink and downlink slot allocation on the centralized scheduling scheme which can abate interferences in the network. This algorithm allows more subscriber stations to transmit concurrently and so improves spatial reuse in the network. Also, the algorithm uses multi-channel and single channel systems and considers relay model, smoothing switching frequently between transmitting and receiving in successive time slots and fairness in the network. Extensive simulation results demonstrate the effectiveness of the proposed method in terms of scheduling length, link concurrency ratio, network throughput and Channel Utilization Ratio (CUR).

An Enhanced Energy Efficiency Tree-Based Hierarchical Routing Based on Additional Connections

Instrumented is defined as a key characteristic in the upcoming smart cites, which demands a higher Wireless Sensor Networks (WSNs) performance. Tree-based Hierarchical Routing (THR) is a routing protocol for WSNs static scenarios. THR hierarchically maps WSN area into a routing tree. However, fixed topology and hierarchical architecture leads to unbalanced energy overhead distribution and inflexible routes selection. To uniformly distribute routing energy overhead, reduce routing hops and extend network life cycle, we designed an enhanced THR routing protocol based on additional connections such as Neighbors, Brothers and Nephews. Based on these connections, three actions were introduced which are Shortcut, Overhead Balancing and Adoption. A simulation for different network loads on OMNet++4.1 is issued, and realized this THR routing in Chipcon SmartRF04?EB embedded boards based on Zigbee in a point-to-point topology. According to the simulation results and experiment data, this proposal obviously improved the latency performance, reduced energy overhead and extended the network’s life cycle.

Subarea Tree Routing (STR) in Multi-hop Wireless Ad hoc Networks

Subarea Tree Routing (STR), a new routing protocol for multi-hop wireless ad hoc networks, is proposed. The novelty of the STR protocol is to divide the whole network into many subareas constructed as a result of establishing subarea trees. Its main idea is to identify root nodes by manual configuration or auto-discovery process firstly, then the root nodes originate the process of establishing subarea trees, and finally each node either joins in a subarea tree or become an interconnect node. STR belongs to hierarchical routing protocol and does not attempt to consistently maintain routing information in every node. Furthermore, through the use of tree’s intrinsic routing function, the STR protocol exhibits hybrid behavior of proactive and on-demand routing protocols. We prove the correctness of STR, and our simulation results show that the pro-posed scheme achieves lower route discovery delays, lower route discovery load and better performance of normalized routing load in large, mobile, ad hoc networks as compared with AODV.

Design Method Based on Routing Tree for Topology Update in Ad Hoc Network

A design method based on the tree-model structure for topology update is presented. The routing tree of every node in network is built by defining the data structure and is used to save the topology information of neighbor nodes. The node topology update is accomplished by exchanging their routing trees. For saving the precious wireless bandwidth, the routing tree is sparsely shaped before sending by pruning the redundant routing information. Then, the node topology update is implemented by using algorithms of inserting and deleting routing sub-trees.

Ant Colony Optimization for Multi-Objective Multicast Routing

In the distributed networks,many applications send information from a source node to multiple destination nodes.To support these applications requirements,the paper presents a multi-objective algorithm based on ant colonies to construct a multicast tree for data transmission in a computer network.The proposed algorithm simultaneously optimizes total weight(cost,delay and hop)of the multicast tree.Experimental results prove the proposed algorithm outperforms a recently published Multi-objective Multicast Algorithm specially designed for solving the multicast routing problem.Also,it is able to find a better solution with fast convergence speed and high reliability.

An Improved Multicast Routing Algorithm

Multicasting is a communication service that allows an application to efficiently transmit copies of data packets to a set of destination nodes. The problem of finding a minimum cost multicast tree can be formulated as a minimum Steiner tree problem in networks, which is NP-completeness. MPH (minimum path cost heuristic) algorithm is a famous solution to this problem. In this paper, we present a novel solution TPMPH (two phase minimum path cost heuristic) to improve the MPH by generating the nodes and the edges of multicast tree separately. The cost of multicast tree generated by the proposed algorithm with the same time as MPH is no more than that of MPH in the worst case. Extensive simulation results show that TPMPH can effectively improve the performance on MPH, and performs better in large-scale networks and wireless networks.

Backtracking Routing Mechanism for Improving Link Failure Recovery

Failure-insensitive routing is a good mechanism to avoid packet dropping and disconnection of forwarding when some links fail, but multiple failure links may bring routing loop for the mechanism. Backtracking routing algorithm based on inverse shortest path tree rooted at destination is presented. The feasible restoration routing is obtained through searching from the start of the failure link and tracing back to the leaves of the shortest path tree with the destination as the root. The packets are forwarded from the mounted point with smaller sequence to the mount point with bigger sequence to decrease the possible of loop in case of multi-failures. The simulations and analysis indicate that backtracking routing algorithm improves the network survivability especially for large network, at the cost of the computation complexity in the same order as failure insensitive routing.

Multicast Routing Based on Hybrid Genetic Algorithm

A new multicast routing algorithm based on the hybrid genetic algorithm (HGA) is proposed. The coding pattern based on the number of routing paths is used. A fitness function that is computed easily and makes algorithm quickly convergent is proposed. A new approach that defines the HGA's parameters is provided. The simulation shows that the approach can increase largely the convergent ratio, and the fitting values of the parameters of this algorithm are different from that of the original algorithms. The optimal mutation probability of HGA equals 0.50 in HGA in the experiment, but that equals 0.07 in SGA. It has been concluded that the population size has a significant influence on the HGA's convergent ratio when it's mutation probability is bigger. The algorithm with a small population size has a high average convergent rate. The population size has little influence on HGA with the lower mutation probability.

A Heuristic Algorithm for Multicast Routing with Delay and Bandwidth Constrains

An improved heuristic algorithm is developed which can optimize the multicast routing under the condition that both delay and bandwidth are constrained. Performance analysis and computer simulation show that the routing mechanism can successfully solve the QoS problem in the case of many-to-many cast session. The scheme can make the cost of routing tree optimized and the bandwidth and end-to-end delay guaranteed. Because complexity of algorithm is limited, it is suitable to deal with networks of large size.

Performance Tradeoff with Routing Protocols for Radio Models in Wireless Sensor Networks

In this paper, we have simulated and evaluated the performance tradeoff with routing protocols: Constrained Flooding, the Real-Time Search and the Adaptive Tree on MICA and MICAz platform with different radio models using PROWLER for wireless sensor networks. The simulation results establish that the MICAz motes give low latency, high throughput, high energy consumption, low efficiency but better lifetime while the MICA motes give high success rate and less loss rate. It has been, thus, concluded that in case of all the radio models the MICAz is preferably better than MICA in applications where energy is a constraint. Moreover, use of MICAz motes increases the network lifetime in comparison to MICA for the radio models. Further, the AT protocol can be applied to achieve better energy consumption, efficiency and lifetime in real time for wireless sensor networks.

Energy-Delay Efficient Unified Routing Protocol for Wireless Sensor Networks

One of the most important challenges in the Wireless Sensor Networks is to improve the performance of the network by extending the lifetime of the sensor nodes. So the focus is on obtaining a trade-off between minimizing the delay involved and reducing the energy consumption of the sensor nodes which directly translate to an extended lifetime of the sensor nodes. An effective Sleep-wake scheduling mechanism can prolong the lifetime of the sensors by eliminating idle power listening, which could result in substantial delays. To counter this, an anycast forwarding scheme that could forward the packet opportunistically to the first awaken node may result in retransmissions as if the chosen node falls in resource constraints. The algorithm, namely Prim’s-Dual is proposed to solve the said problem. The algorithm considers five crucial parameters, namely the residual energy of the nodes, transmission power, receiving power, packet loss rate, interference from which the next hop is determined to extend the lifetime of the sensor node. Since the proposed work is framed keeping critical event monitoring in mind, the sleep-wake scheduling is modified as low-power, high-power scheduling where all nodes are in low-power and the nodes needed for data transmission are respectively turned on to high-power mode. The integrated framework provides several opportunities for performance enhancement for conflict-free transmissions. The aim of our algorithm is to show reliable, energy efficient transfer without compromising on lifetime and delay. The further effectiveness of the protocol is verified. The results demonstrate that the proposed protocol can efficiently handle network scalability with acceptable latency and overhead.

ROUTING AND WAVELENGTH ASSIGNMENT ALGORITHMS BASED ON EQUIVALENT NETWORKS

In this paper, a Wavelength Division Multiplexing (WDM) network model based on the equivalent networks is described, and wavelength-dependent equivalent arc, equivalent networks, equivalent multicast tree and some other terms are presented. Based on this model and relevant Routing and Wavelength Assign- ment (RWA) strategy, a unicast RWA algorithm and a multicast RWA algorithm are presented. The wave- length-dependent equivalent arc expresses the schedule of local RWA and the equivalent network expresses the whole topology of WDM optical networks, so the two algorithms are of the flexibility in RWA and the optimi- zation of the whole problem. The theoretic analysis and simulation results show the two algorithms are of the stronger capability and the lower complexity than the other existing algorithms for RWA problem, and the complexity of the two algorithms are only related to the scale of the equivalent networks. Finally, we prove the two algorithms’ feasibility and the one-by-one corresponding relation between the equivalent multicast tree and original multicast tree, and point out the superiorities and drawbacks of the two algorithms respectively.

MTree_Nix网络模拟路由计算与查找策略

提出并实现了Nix-Vector的改进—MTree_Nix路由策略.MTree_Nix以若干棵最小生成树作为基本路由表,对不能被最小生成树覆盖的路由信息则采用Nix-Vector策略进行实时计算.通过分析MTree_Nix的存储空间和路由查找时间,找到二者之间达到最优平衡的条件.比较实验结果表明,MTree_Nix路由策略模拟时间比Nix-Vector节省85%.