65 results about "Tree routing" patented technology

A method and system for re-routing interconnects within an integrated circuit design having blockages and bays is disclosed. A net within the integrated circuit design is initially decomposed into multiple two-paths. The net includes interconnects previously routed by utilizing a Steiner tree routing algorithm. Next, a cost associated with each of the two-paths is calculated. A two-path having a a high cost is subsequently selected and re-routed with a lower cost two-path.

A routing method of a wireless communication system is provided implementing advantageous features of both the tree routing and the link state routing. In the routing method, the system generates an adaptive tree table which defines a network in a tree structure of at least one branch with at least one node and each node generates a link state table which includes information on neighbor nodes, such that the packets are routed on the basis of the adaptive tree table and the link state table. Advantageous mechanisms of the tree routing and the link state routing are combined, thereby it is possible to eliminate most single point of failures of conventional tree routing and provide shorter paths compared with conventional tree routing.

A method for relaying a route request RREQ message by an intermediate node which is connected with at least one node using a tree topology in a mobile communication system including a destination node and a source node which sends the RREQ message to the destination node via at least one intermediate node, to thus establish an optimal route for communications. The RREQ message is received along the route other than the tree route, and the first information is updated using its information. The intermediate node relays to a next intermediate node the RREQ message containing the updated first information.

The invention relates to a method for routing a queue tree in a wireless self-organization network applicable to a monitoring system. The invention includes a routing generation process, a dynamic maintenance of the routing and a monitoring data amalgamation transmission based on routing arithmetic. A network node selects the neighboring node with a small hot count to send a routing establishment request, and according to a handshaking mechanism, a routing relationship between an upper level and a lower level is established, and the whole network is formed a plurality of tree routing structures; according to ways of a connection detection, a past-due detection and upper node switching, a dynamic maintenance of the routing is realized, changes in network communication topology caused by factors such as the motion of the node and power change are adapted; by using the network structure of the tree routing, the node is able to inosculate the a communication desire to monitor the data in due time at the same time of maintaining the route. The method of the invention has the advantages of low spending on the communication, small delay of transmission and steady and reliable network.

The invention discloses an IPv6 over low power wireless personal area network (6LoWPAN) neighbor discovery-based tree routing method, which relates to the field of wireless sensor networks and comprises the following steps of: a, when a 6LoWPAN sensor node is added into the network, establishing a root node of tree topology, and configuring the basic information of the network to the root node; b, adding other ordinary nodes into the network; and c, forming routing. Moreover, the step c comprises the following steps of: under any one of the three conditions of leaf node invalidation or leaving, non-leaf node invalidation or leaving and node movement, triggering a routing restoring process; and under any one of the three conditions of no leaf node invalidation or leaving, no non-leaf node invalidation or leaving and no node movement, finishing the processing. In the 6LoWPAN neighbor discovery-based tree routing method, an additional routing protocol message is not required to be transmitted and received, so the bandwidth and the routing calculation overhead are reduced, energy consumption produced in the message transmission of the nodes is saved, and the energy consumption and routing overhead of the whole network are further reduced.

The disclosed multilayer tree route method for distributive certification of wireless self-organizing network comprises the group generation, route group maintenance and group selection. The key of this invention is to reconstruct the network structure into a multilayer group tree topology. This invention improves certification efficiency, reduces network spending, and improves the network security and reliability.

Provided is a routing method capable of expanding a conventional tree routing to perform the efficient and safe key management in a sensor network environment that requires the symmetric key based key management. Each sensor node transmits a Route Reverse message to a sink node to set a reverse tree routing path. Therefore, it is possible to provide efficient and safe key management mechanism and communication environment by providing a bidirectional communication between a sink node and sensor nodes through an expanded tree routing such that a user is provided with a safe sensor network.

The invention discloses a ZigBee sensor network tree route low-expense optimization method. The method comprises four stages of route finding packet sending, route finding packet processing, reply packet sending and reply packet processing. The flooding operation in the ZigBee sensor network tree route optimization process is limited in the aspects of transmitting nodes and hop count range of the route finding packet, so that flooding expense is obviously reduced. Meanwhile, intermediate nodes are allowed to reply the route finding packet, the flooding expense can be further lowered, and the route finding time delay of the optimal route can be reduced. Moreover, the energy optimal route can be selected in the condition of multiple routes by designing a new route length measurement mechanism, namely synthesized hop count, for simultaneously reflecting the hop count and node residual energy, node energy consumption is balanced, and the node survival time and network service life are prolonged.

A method for relaying a route request RREQ message by an intermediate node which is connected with at least one node using a tree topology in a mobile communication system including a destination node and a source node which sends the RREQ message to the destination node via at least one intermediate node, to thus establish an optimal route for communications. The RREQ message is received along the route other than the tree route, and the first information is updated using its information. The intermediate node relays to a next intermediate node the RREQ message containing the updated first information.

Provided is a method of preventing a data collision that occurs when two or more child nodes simultaneously transmit data to a parent node in a ZigBee network having a tree routing scheme and operating in a beacon mode. In the ZigBee system having the tree routing scheme and operating in the beacon mode, data communication to the parent node is performed in a beacon frame of the parent node. Here, when several child nodes exist under a single parent node, the child nodes transmit data to the parent node at the moment of receiving the beacon of the parent node, so that the data collision may occur when the child nodes simultaneously transmit the data to the parent node in the beacon frame of the parent node. In the method of preventing a data collision, each of the two or more child nodes is set to wait for its guard time (delay time) when transmitting data to the parent node to induce a normal slotted carrier sense multiple access with collision avoidance (CSMA-CA) operation. Therefore, the data collision can be prevented.

Systems and methods for improving the performance of dynamic router table data structures are provided. The invention relates to methods and systems for partitioning prefixes or prefix-based intervals. In one embodiment, priority search tree router data structures are applied to prefix partitions of the present invention. In another embodiment, basic-interval tree and prefix tree data structures are applied to interval partitions of the present invention.

The invention discloses an HWMP-based double route cooperation method. With the method, a problem that forwarding for internetwork node communication needs gateway nodes in the prior art can be solved. The method comprises: step one, a prior tree route is established; step two, a node identifier is added to a data frame by a source node and whether a route connected to a destination node exists is searched in a route table; step three, according to a searching result, the data frame is forwarded to the destination node or a root node; step four, the root node searches whether a route connected to the destination node exists in the route table to set a destination node type so as to carry out data forwarding; and step five, after the destination node receives the data frame, whether an on-demand route is triggered is determined based on the identifier in the data frame; and if so, the data frame is sent according to an optimal route; and otherwise, the data frame is sent according to an original route. Therefore, the transmission delay is reduced; and the data sending performance is improved. The method can be applied to the communication services of nodes in the internet and internetwork nodes in a wireless mesh network.

The invention discloses a route construction method with a strong source position privacy protection capacity. The route construction method comprises the following steps: firstly, creating a phantom node P according to the existing phantom routing policy; secondly, creating a first branch route formed by PA and PT by the phantom node P according to set hop count fai; thirdly, creating a main trunk routing path by a middle node A; finally, creating interference branch routes by nodes on the main trunk routing path. According to the method, only the main trunk routing path is created in an area with high network energy consumption, and the energy consumption of an energy cavity area is not increased, thus the life of a network is not reduced, the excess energy away from Sink area nodes is adequately utilized, and the interference branch routes are created as much as possible in an area with adequate energy; a very strong source position privacy protection capacity can be achieved on the basis of the novel tree routing policy of redundancy interference routing paths, meanwhile, the network achieves energy balance, and the life of the network is maximized.

A method and device are disclosed. In one embodiment the method includes driving a first clock domain reference signal on a first clock tree and driving a second clock domain reference signal on a second clock tree. The first tree routes the first signal from a PLL to a first clock domain drop off circuit and the second tree routes the second signal from the PLL to a second clock domain drop off circuit. A jitter produced from the second tree is less than a jitter produced from the first tree. The method continues by detecting any phase misalignment between the first signal and the second signal. The method also causes the first signal to be delayed so that it aligns with the second signal.

The invention provides a sensor network-oriented approximate query method commonly used for privacy protection. The method includes the following steps that the shared data structure of a base station and sensor nodes is used for enabling the numbers and collection data of the sensor nodes to be hidden in a vector; gathering nodes transmit the vector to the base station through a tree route; a linear system of equations is constructed in the base station, and a column diagram with global statistical information and a corresponding sensor node number are solved; the needed approximate query is completed according to the statistical information of the column diagram. According to the sensor network-oriented approximate query method, under the condition that privacy information is not leaked, approximate query energy consumption is reduced by the adoption of the strategies like network internal data gathering and a filter, and under the condition that the model does not need to be modified, accuracy control over the privacy protection approximate query can be achieved by the way of parameter adjustment.

The invention relates to an internet-of-things self-organizing network protocol based on a tree routing algorithm and belongs to the technical field of telecommunications. The algorithm comprises the following three steps of: searching child nodes, searching the nearest neighboring nodes and searching ancestor nodes. The tree routing algorithm is properly improved, the address, depth and other information of the neighboring nodes are added in the nodes, when the routing is searched, the routing length is effectively reduced, the energy consumption of the nodes is obviously reduced, and the problem of a routing list of Ad hoc ondemand distance vector junior (AODVjr) is avoided.

The invention proposes a recovery method for multicasting service connection in an automatically switched optical network, which includes the following steps: a root node calculates and establishes an optical multicasting tree according to a multicasting service demand and sets multicasting service attribute and a multicasting ID, and simultaneously sets recovery strategy for branch nodes; various network elements in a network detect that a fault happens to nodes and / or links; the node network element detecting the fault searches for the service connection on the invalid link and / or the service connection among the invalid network elements; if the service connection comprises the multicasting service connection, the node network element sends the signaling message containing the invalid link and / or invalid node to the branch node network element of the multicasting service connection; the branch node combining the set recovery strategy recalculates one restoration route or one restoration multicasting tree route with the branch node network element serving as a source and a leaf node influenced by the fault serving as a destination; and the branch node starts signaling process of establishing the restoration route or the restoration multicasting tree and sets the attribute and the multicasting ID same in the original service connection for the new service connection.

The invention provides a link restoration method for an HWMP priori tree route mode. The method is used for solving the technical problem that in the prior art, low path maintenance cost and short path recovery delay cannot be both taken into consideration. The method comprises steps that a root node broadcasts RANNs periodically; general nodes receive multiple RANN frames; MAC addresses of the backup father nodes and the father nodes of the general nodes are stored; a priori tree route from the general nodes to the root node is established; a current general node carries out unicast on a data packet to the root node; whether a link is disconnected or not is judged by whether ACK replied by the father node is received or not; and the disconnected link from the current general node to the root node is restored by employing a backup father node method, a local link method or a route tree reestablishment method. The method is characterized in low network load and short restoration delay, can be applied to rapid restoration of the disconnected link in the prior tree route of a wireless mesh network WMN.

Some embodiments provide a method of pre-computing routes for nets in a region of a circuit layout. The method initially defines a set of partitioning lines for partitioning the region into a plurality of sub-regions during a routing operation. The method then identifies a primary set of sub-regions that has more than one sub-region. It then determines whether the primary set of sub-regions is an open set that has a sub-region that is not adjacent to any other sub-region in the set. If the primary set of sub-regions is not an open set, the method identifies a route that connects the sub-regions in the primary set, and stores the identified route for the primary set of sub-regions. On the other hand, if the primary set of sub-regions is an open set, the method identifies a connection set of sub-regions that when combined with the primary set forms a closed set of sub-regions that (i) does not have any sub-region that is not adjacent to another sub-region in the closed set, and (ii) can be traversed by a minimum tree route that connects each sub-region in the connection set to at least two other sub-regions in the primary and connection sets of sub-regions. For the primary set of sub-regions, the method then stores at least either the connection set of sub-regions or the closed set of sub-regions.

A routing method of a wireless communication system is provided implementing advantageous features of both the tree routing and the link state routing. In the routing method, the system generates an adaptive tree table which defines a network in a tree structure of at least one branch with at least one node and each node generates a link state table which includes information on neighbor nodes, such that the packets are routed on the basis of the adaptive tree table and the link state table. Advantageous mechanisms of the tree routing and the link state routing are combined, thereby it is possible to eliminate most single point of failures of conventional tree routing and provide shorter paths compared with conventional tree routing.

The invention discloses a method for realizing energy conservation of a wireless sensing node in a greenhouse tomato irrigating system. A ZigBee tree routing mechanism is improved through analyzing the requirement of tomato irrigating environment information and a ZigBee tree routing algorithm; during the data forwarding process of a sensing node, a next-hop routing node is selected by an energy comprehensive evaluation function; during the irrigation decision-making process, a coordinator judges whether the irrigation is needed according to the illumination, air temperature, humidity, relative humidity of the soil, and the current crop growth cycle acquired by the sensing node; when the irrigation is not needed, the coordinator predicts when the irrigation is needed; and prior to this process, the sensing node is in a dormancy state. By the improved ZigBee tree routing and the coordinator irrigation decision-making data request mechanism of the invention, the transmission of a data packet in an overall wireless sensing network is greatly reduced, the energy utilization ratio of the node is effectively improved, and the stable period of the wireless sensing network is prolonged.

A gateway selection method for a wireless mesh network is provided for selecting an optimal gateway includes building a spanning routing tree to a given network. Reference factors of routers are calculated regarding the network to total network capacity in association with the spanning routing tree. A router is selected which has the greatest reference factor as being an optimal gateway of the network.

The invention discloses a genetic algorithm based minimum-cost optical multicast tree routing method. The method includes two parts of edge initialization of a network and minimum-cost multicast tree iteration. The edge initialization of the network mainly includes completing initialization of edges in the network, representing the edges with integer multiples of unit capacity with multiple unit capacity edges, and conveniently applying a genetic algorithm to optimize an information transmission path and an encoding method. The minimum-cost optical multicast tree iteration mainly includes the steps of selection, intersection, variation, bad gene removal and the like. Some bad genes are removed from a gene pool according to a designed fitness function value in the process of iteration every time, so that size of an algorithm searching space can be greatly decreased, convergence rate of the algorithm is increased beneficially, and an optical multicast tree with less cost is found out. The information transmission routing method is smallest in total number of found and needed information transmission links meeting the requirement on multicast request rate, and minimum in encoding operation times.

A method and device are disclosed. In one embodiment the method includes driving a first clock domain reference signal on a first clock tree and driving a second clock domain reference signal on a second clock tree. The first tree routes the first signal from a PLL to a first clock domain drop off circuit and the second tree routes the second signal from the PLL to a second clock domain drop off circuit. A jitter produced from the second tree is less than a jitter produced from the first tree. The method continues by detecting any phase misalignment between the first signal and the second signal. The method also causes the first signal to be delayed so that it aligns with the second signal.

The invention discloses a dynamic clustering based multi-gateway WMN load balancing realization method in presence of IEEE802.11s. The dynamic clustering based multi-gateway WMN load balancing realization method in presence of IEEE802.11s comprises the steps of regarding a gateway node as a cluster head and a gateway MAC address as a cluster identifier; adding the cluster head and the cluster identifier in an RANN frame and a PREQ frame to realize cluster selection and cluster segmentation of a common node; modifying the processing process of the PREP frame and the PERR frame to maintain a transcendental tree routing and realize smooth transition of a routing list and a gateway load when the cluster of the node is changed; and giving comprehensive consideration to the path Metric from the node to the gateway and the load condition of the gateway per se when the common node selects the cluster, and selecting an optimal gateway to realize the purpose of balancing the gateway load, wherein the load volume is the proportion of the length of a transmission queue buffering region of a wired network card of a gateway node to the total length of the queue, and is added in the RANN frame for broadcasting. According to the dynamic clustering based multi-gateway WMN load balancing realization method in presence of IEEE802.11s, the dynamic clustering based multi-gateway wireless Mesh network and gateway load balancing is realized, the network overhead is reduced, the gateway load is balanced and the performance of the whole network is accordingly improved.

The invention relates to a hierarchical link tree routing method based on region partition. The method comprises the following steps: 1, partitioning a wireless sensor network into a plurality of regions; 2, separately clustering each region, and forming a first link in each corresponding region by using nodes in each cluster through a generic algorithm according to a PEGASIS (Power-Efficient Gathering in Sensor Information Systems) protocol; 3, selecting a cluster head from each cluster according to an energy maximum principle; 4, forming a second link by using a communication link between each cluster head and a Sink node through a generic algorithm according to the PEGASIS protocol; 5, transforming the second link into a hierarchical link tree taking the Sink node as the center; 6, transmitting node data to the Sink node through data fusion along the hierarchical link tree, and skipping to the step 1 after preset communication time. By adopting the hierarchical link tree routing method, the energy consumption of long-distance communication caused by the adoption of a single-hop way among nodes in a LEACH (Low Energy Adaptive Clustering Hierarchy) algorithm is lowered effectively.

The invention discloses a compressed data collection method for a mobile wireless sensor network, which comprises the following steps of: firstly, designing a Treelet-based sparse representation baseby utilizing the space-time correlation of sensor node perception data; secondly, designing a sparse random measurement matrix; then, designing a Brown tree routing algorithm for data collection; andfinally, carrying out compressed data reconstruction at the Sink node according to the sparse representation base, the sparse random measurement matrix and the Brown tree route. By adopting the method, the data collection efficiency of the sensor network can be improved, the total cost of the nodes of the sensor network is reduced, and the life cycle of the network is prolonged to a certain extent.

The invention discloses a network time delay optimization method for a multi-alliance chain consensus algorithm, and the method comprises the following steps: constructing a multicast tree for each alliance chain in a communication network topology by utilizing a reinforcement learning technology through a routing controller, wherein a main node of the alliance chain is taken as a root node of each multicast tree; constructing a multicast tree which ensures that the main node is communicated with all the auxiliary nodes, so that a block generated by the main node can be routed to all member nodes through the multicast tree; besides, enabling the routing controller to allocate bandwidth to each path on each multicast tree, wherein in the bandwidth allocation process, delay indexes of all alliance chains on each edge need to be considered, and the sum of bandwidth occupancy of all chains on the same edge cannot exceed the total available bandwidth of the link; and finally, enabling the routing controller to deploy the multicast tree routing and the bandwidth allocation result into the communication network, thereby completing the time delay optimization of the communication network.