Method for discovering multiple routes in sensor networks

• US 8,861,398 B2
• Filed: 03/31/2011
• Issued: 10/14/2014
• Est. Priority Date: 06/30/2009
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Bhatti, Ghulam M, Guo, Jianlin, Zhang, Jinyun, Teo, Koon Hoo
• Primary Examiner(s): Wong, Warner
• Application Number:
  US13/077,327
• Publication Number:
  US 20110176416A1
• Time in Patent Office: 1,293 Days
• Field of Search: 370/254, 370/255, 370/351, 370/373, 370/37, 370/384, 370/389, 370/392, 370/410, 370/426, 370/496, 370/522, 709220-222
• US Class Current: 370/254
• CPC Class Codes: G01D 2204/45 Utility meters networked together within a single building
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04N 7/18 Closed-circuit television [CCTV] systems, i.e. systems in which the video signal is not broadcast
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02B 90/20 Smart grids as enabling technology in buildings sector smart grids supporting the management or operation of end-user stationary applications in general, or like technologies with no associated climate change mitigation effect Y04S20/00
• CPC Class Codes: Y04S 20/30 Smart metering, e.g. specially adapted for remote reading

Abstract

Multiple routes from a data source node to multiple data destination nodes in a large scale multi-hop mesh network are discovered. Nodes discover multiple routes to two destinations in an initial discovery phase that includes only two network-wide flooding of packets. The method can also work with one destination. The method can be extended to include more destinations with a proportional increase in the communication overhead. After the completion of the discovery phase, nodes can communicate or forward their own or received data by using any of the available routes.

Claims

1. A method for discovering multiple routes in a multi-hop network including a set of source nodes and a set of destination nodes such that each source node discovers the multiple routes to all the destination nodes to transmit data from the source node using one of the discovered routes to a particular destination node, comprising the steps of:

broadcasting, by each source node, a route request (RREQ) packet to initiate discovering the multiple routes to the set of destination nodes, wherein the RREQ packet includes routing information and a cost field;

receiving, in neighboring intermediate nodes of the source node, one or more copies of the RREQ packet;

updating, in the neighboring source nodes, the routing information and cost field;

broadcasting, by the neighboring intermediate nodes in response to receiving the one or more copies of the RREQ packet, at least one copy of the RREQ packets to other neighboring intermediate nodes until one or more copies of the RREQ packet are received by the destination nodes;

constructing, in each destination node, a route reply (RREP) packet, for every received RREQ packet, wherein the RREP packet includes routing information and a cost field;

broadcasting, by each destination node to the neighboring, the RREP packet;

receiving, in neighboring intermediate nodes of the destination node, one or more copies of the RREP packet;

updating, in the neighboring intermediate nodes, the routing information and cost field; and

broadcasting, by the neighboring intermediate nodes in response to receiving the one or more copies of the RREP packet, at least one copy of the RREP packets to other neighboring intermediate nodes until the one or more copies of the RREP packet are received by each source node so that each source node can select one of the multiple routes to send data to the one of the destination nodes based on die routing information and the cost field in one of the RREP packets.

2. The method of claim 1, wherein the network is flooded with the RREQ packets and the RREP packets for no more than k+1 times, where k is the number of destination nodes.

3. The method of claim 1, wherein the multiple routes are discovered periodically.

4. The method of claim 1, wherein the multiple routes are discovered non-periodically.

5. The method of claim 1, wherein each source node is a meter node, and each destination node is a concentrator node connected to an operating center of a utility provider.

6. The method of claim 1, wherein the nodes are connected by wireless links.

7. The method of claim 1, wherein the multiple routes include one or more primary routes, and one or more backup routes.

8. The method of claim 1, wherein the RREQ packet includes a transmitting node address, a RREQ Id, a source address, a destination address, a reverse cost, a hop count, and the RREP packet includes the transmitting node address, the RREP Id., the source address, the destination address, a forward cost, the reverse cost, and the hop count.

9. The method of claim 8, wherein the forward cost is based on a combination of the hop count, a link quality, an average packet drop rate, a buffering capacity, and an expected transmission delay.

10. The method of claim 1, wherein the intermediate nodes may discard any subsequently received copies of the same RREQ packet.

11. The method of claim 1, further comprising:

eliminating cycles from the multiple routes by a union of the routes to the destination node form a logical tree structure.

12. The method of claim 1, further comprising:

rejecting any route that intersects another route.

13. The method of claim 1, wherein the cost includes a forward cost and a backward cost, and a function of the forward cost and the backward cost determine the cost of a particular route.

14. The method of claim 1, wherein a list of all nodes traversed by the RREQ packets and the RREP packets is stored in each packet.

17. The method of claim 1, wherein routes longer than a predefined threshold are rejected.

18. The method of claim 1, wherein the RREQ packet specifies one destination node as the target of a route discovery or it specifies a set of destination nodes to which routes are discovered simultaneously.

19. The method of claim 1, wherein ever data source node N_i can maintain a local database to keep R_i1>

0 best routes to a destination node D₁, R_i2>

0 best mutes to a destination node D₂, and so on depending on its available storage capacity and importance of destination nodes, wherein the value of R_i1 and R_i2 may or may not be same.

20. The method of claim 1, wherein the source, intermediate and destination nodes are connected by wireless links or any other short range communication technology such as power line communication (PLC) systems.

15. A method for discovering multiple routes in a multi-hop network including a set of source nodes and a set of k destination nodes, comprising the steps of:

broadcasting, by each source node, a route request (RREQ) packet to initiate discovering the multiple routes to the set of k destination nodes;

receiving one or more copies of the RREQ packet in each of the set of k destination nodes;

broadcasting by each of the set of k destination nodes, a route rep (RREP), in response to the receiving; and

receiving in each destination node one or more copies of the RREP packet, wherein the network is flooded with the RREQ packets and the RREP packets for no more than k+1 times.

16. The method of claim 15, wherein each RREQ packet and each RREP packet includes one or more routes from the source node to the one or more of the set of k destination nodes and a cost associated with each route;

and further comprising;

selecting one of the routes to transmit data to a particular destination node based on the cost.