Method and apparatus for locating communities over an ad-hoc mesh network

• US 8,856,252 B2
• Filed: 08/20/2012
• Issued: 10/07/2014
• Est. Priority Date: 05/29/2009
• Status: Active Grant

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Leppanen, Kari, Turunen, Markku T., Virtanen, Sami, Tirronen, Mikko, Kasslin, Mika
• Primary Examiner(s): DAILEY, THOMAS J
• Application Number:
  US13/589,971
• Publication Number:
  US 20120314660A1
• Time in Patent Office: 778 Days
• Field of Search: 709/206, 370/328
• US Class Current: 709/206
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04L 51/58 Message adaptation for wireless communication
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 4/21 for social networking applications
• CPC Class Codes: H04W 4/50 Service provisioning or reconfiguring
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• 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

Abstract

An approach is provided for locating communities over an ad-hoc mesh network. Community identifiers are used to locate communities and community members over an ad-hoc mesh network. The community identifiers are also associated with keys to authenticate members of the community and to protect the privacy and anonymity of information exchanged between the members.

Claims

1. A method comprising:

discovering local information by broadcasting an anonymous propagating multi-hop flooding message over a wireless ad-hoc mesh network,

wherein broadcasting the anonymous propagating multi-hop flooding message comprises transmitting to neighboring nodes in connectionless manner without a need to send any prior control signals or messages to neighboring nodes before the transmission, and without knowledge of addresses of the neighboring nodes,

wherein, in a pull mode of broadcasting the anonymous propagating multi-hop flooding message, the method further comprises;

distributing a query from an originating node to the neighboring nodes,

creating routing information using the query alone to route a reply back to the originating node, and

supplying awareness information back to the originating node as the reply using the routing information, and

wherein, in a push mode of broadcasting the anonymous propagating multi-hop flooding message, the method further comprises;

distributing awareness information from one neighboring node to another neighboring node without routing information.

2. A method of claim 1, further comprising:

in the pull mode of dissemination, providing the awareness information to the originating node as an automatic reply from a node of the wireless ad-hoc mesh network that has the awareness information.

3. A method of claim 1, further comprising:

in the push mode of dissemination, storing the distributed awareness information in one or more nodes of the wireless ad-hoc mesh network through which the multi-hop flooding message propagates.

4. A method of claim 1, further comprising:

storing, in a routing table of a node, a list of node identification numbers of the originating node and of last known transmitters of the anonymous propagating multi-hop flooding message.

5. A method of claim 1, further comprising:

identifying a community of a plurality of wireless nodes using a community identifier corresponding to the community by broadcasting a community search message over a wireless ad-hoc mesh network,

wherein the community search message propagates to all devices that are in proximity in the community whether they belong to the community or not.

6. A method of claim 5, further comprising:

receiving input requesting a search for one or more members of the community;

retrieving a community pseudonym corresponding to the community;

generating a member search message containing a community query identifier and the community pseudonym;

initiating transmission of the member search message to one or more neighboring wireless nodes, wherein each neighboring wireless node that is visible and that is associated with the community pseudonym automatically replies to the member search message; and

updating a list of visible community members based on one or more replies to the member search message.

7. A method of claim 6, further comprising:

identifying the community as an active community if at least one reply is received in response to the member search message; and

updating the list of active communities based on the identification.

8. A method of claim 5, further comprising:

monitoring for one or more messages related to the community over a predetermined period of time;

designating the community as an inactive community if no messages related to the community are observed during the predetermined period of time; and

updating the list of active communities based on the designation.

9. A method of claim 5, wherein to join a wireless node to the community, the method further comprises:

receiving at the wireless node, over a secure communication channel, the community identifier and a corresponding authentication key, and

storing the received community identifier and the corresponding authentication key in a community directory within the wireless node.

10. A method of claim 5,

wherein, the community is specific to a first wireless node and a second wireless node, and represents a bond between the first wireless node and the second wireless node, and the method further comprises:

creating the community by exchanging the community identifier and a corresponding authentication key between the first wireless node and the second wireless node, and

wherein, to discover other wireless nodes which have a bond with the first wireless node, the method further comprises;

broadcasting from the first wireless node community search messages containing a pseudonym corresponding to the community of the first wireless node related to this bond.

11. An apparatus comprising:

at least one processor; and

at least one memory including computer program code,

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following;

discover local information by broadcasting an anonymous propagating multi-hop flooding message over a wireless ad-hoc mesh network,

wherein broadcasting the anonymous propagating multi-hop flooding message comprises transmitting to neighboring nodes in connectionless manner without a need to send any prior control signals or messages to neighboring nodes before the transmission, and without knowledge of addresses of the neighboring nodes,

wherein, in a pull mode of broadcasting the anonymous propagating multi-hop flooding message, the apparatus is further caused to;

distribute a query from an originating node to the neighboring nodes,

create routing information using the query alone to route a reply back to the originating node, and

supply awareness information on demand back to the originating node as the reply using the routing information,

wherein, in a push mode of broadcasting the anonymous propagating multi-hop flooding message, the apparatus is further caused to;

distribute awareness information from one neighboring node to another neighboring node without routing information.

12. An apparatus of claim 11, wherein the apparatus is further caused to:

in the pull mode of dissemination, provide the awareness information to the originating node as an automatic reply from a node of the wireless ad-hoc mesh network that has the awareness information.

13. An apparatus of claim 11, wherein the apparatus is further caused to:

in the push mode of dissemination, store the distributed awareness information in one or more nodes of the wireless ad-hoc mesh network through which the multi-hop flooding message propagates.

14. An apparatus of claim 11, wherein the apparatus is further caused to:

store, in a routing table of a node, a list of node identification numbers of the originating node and of last known transmitters of the anonymous propagating multi-hop flooding message.

15. An apparatus of claim 11, wherein the apparatus is further caused to:

identify a community of a plurality of wireless nodes using a community identifier corresponding to the community by broadcasting a community search message over a wireless ad-hoc mesh network,

wherein the community search message propagates to all devices that are in proximity in the community whether they belong to the community or not.

16. An apparatus of claim 15, wherein the apparatus is further caused to:

receive input requesting a search for one or more members of the community;

retrieve a community pseudonym corresponding to the community;

generate a member search message containing a community query identifier and the community pseudonym;

initiate transmission of the member search message to one or more neighboring wireless nodes, wherein each neighboring wireless node that is visible and that is associated with the community pseudonym automatically replies to the member search message; and

update a list of visible community members based on one or more replies to the member search message.

17. An apparatus of claim 16, wherein the apparatus is further caused to:

identify the community as an active community if at least one reply is received in response to the member search message; and

update the list of active communities based on the identification.

18. An apparatus of claim 15, wherein the apparatus is further caused to:

monitor for one or more messages related to the community over a predetermined period of time;

designate the community as an inactive community if no messages related to the community are observed during the predetermined period of time; and

update the list of active communities based on the designation.

19. An apparatus of claim 15, wherein, to join a wireless node to the community, the apparatus is further caused to:

receive at the wireless node, over a secure communication channel, the community identifier and a corresponding authentication key, and

storing the received community identifier and the corresponding authentication key in a community directory within the wireless node.

20. An apparatus of claim 15,

wherein, the community is specific to a first wireless node and a second wireless node, and represents a bond between the first wireless node and the second wireless node, and the apparatus is further caused to:

create the community by exchanging the community identifier and a corresponding authentication key between the first wireless node and the second wireless node, and

wherein, to discover other wireless nodes which have a bond with the first wireless node, the apparatus is further caused to;

broadcast from the first wireless node community search messages containing a pseudonym corresponding to the community of the first wireless node related to this bond.