AD HOC NETWORK, NODE, ROUTING CONTROL METHOD AND ROUTING CONTROL PROGRAM

• US 20080126565A1
• Filed: 06/29/2007
• Published: 05/29/2008
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Ishikawa, Norihiro, Uchida, Yoshitaka, OSANO, Tomoyuki
• Granted Patent: US 7,970,933 B2
• Time in Patent Office: Days
• US Class Current: 709/242
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

An ad hoc network is configured of a plurality of nodes. The node includes: a link setting unit configured to set a plurality of links to a plurality of adjacent nodes on a one-to-one basis; a Bloom filter storage unit configured to store a Bloom filter in association with each of the links existing in linked destinations, the Bloom filter generated by using, as a key, a node identification uniquely identifying each of the nodes exiting in linked destination; and a data transmitter configured to use the stored Bloom filters as routing information at a time of data transmission.

Claims

1. An ad hoc network comprising a plurality of nodes, wherein each node comprises:

a link setting unit configured to set a plurality of links to a plurality of adjacent nodes on a one-to-one basis;

a Bloom filter storage unit configured to store a Bloom filter in association with each of the links, the Bloom filter generated by using, as a key, a node identification uniquely identifying each of the nodes existing in linked destinations; and

a data transmitter configured to use the stored Bloom filters as routing information at a time of data transmission.

2. A node in an ad hoc network configured of a plurality of nodes, comprising:

a link setting unit configured to set a plurality of links to a plurality of adjacent nodes on a one-to-one basis;

a Bloom filter storage unit configured to store a Bloom filter in association with each of the links existing in linked destinations, the Bloom filter generated by using, as a key, a node identification uniquely identifying each of the nodes existing in linked destinations; and

a data transmitter configured to use the stored Bloom filters as routing information at a time of data transmission.

3. The node according to claim 2, further comprising an addition processor configured to add a bit string to the Bloom filter storage unit as a Bloom filter corresponding to a link to a participating node that newly participates in the ad hoc network, when the bit string is received tom the participating node, the bit string obtained by conversion of the node identification of the participating node.

4. The node according to claim 3, wherein the addition processor transmits a result of computation to the participating node, the computation carried out by using the Bloom filters of the respective links except the link to the participating node, and using the bit string obtained by conversion of its own node identification.

5. The node according to claim 2, further comprising an update request message transmitter configured to transmit an update request message requesting for Bloom filter update when there is a change in a link to an adjacent node, the update request message transmitted to each of the links except the changed link.

6. The node according to claim 2, further comprising:

an update processor configured to judge whether or not to update the stored Bloom filter when receiving an update request message requesting for Bloom filter update, and to update the stored Bloom filter in response to an affirmative judgment result; and

an update request message transmitter configured to transmit the update request message to each of the links except the link corresponding to the updated Bloom filter.

7. The node according to any one of claims 5 and 6, wherein, when the update request is accepted, the update request message transmitter transmits a result of computation to a node accepting the update request, the computation carried out by using Bloom filters corresponding to the respective links except the link to the node accepting the update request, and using the bit string obtained by conversion of its own node identification.

8. The node according to claim 2, wherein the data transmitter makes a comparison with the stored Bloom filter of each of the links by using, as a search key, a node identification of a destination node to which data is to be transmitted, and selects a link through which the data is to be transmitted, among the plurality of links, according to the comparison result.

9. A routing control method applied to an ad hoc network configured of a plurality of nodes, comprising the steps of:

setting a plurality of links to a plurality of adjacent nodes on a one-to-one basis in each node;

storing a Bloom filter in association with each of the links in each node, the Bloom filter generated by using, as a key, a node identification uniquely identifying each of the nodes existing in linked destinations; and

using, by each node, the stored Bloom filters as routing information at a time of data transmission.

10. A routing control program used for an ad hoc network configured of a plurality of nodes, causing each node to execute the steps of:

setting a plurality of links to a plurality of adjacent nodes on a one-to-one basis;

storing a Bloom filter in association with each of the links, the Bloom filter generated by using, as a key, a node identification uniquely identifying each of the nodes existing in linked destinations; and

using the stored Bloom filters as routing information at a time of data transmission.