Addressing and Routing Scheme for Distributed Systems

• US 20110299425A1
• Filed: 02/11/2010
• Published: 12/08/2011
• Est. Priority Date: 02/12/2009
• Status: Abandoned Application

• Current Assignee: Praveen Kumar
• Original Assignee: Praveen Kumar
• Inventors: Kumar, Praveen
• Application Number:
  US13/201,326
• Publication Number:
  US 20110299425A1
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 2101/681 using addresses for wireless personal area networks or wireless sensor networks, e.g. Zigbee addresses
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 61/5038 for local use, e.g. in LAN or USB networks, or in a controller area network [CAN]
• CPC Class Codes: H04L 61/5061 Pools of addresses
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing

Abstract

The embodiments herein relate to distributed systems and more particularly, to logical address allocation and data routing in a distributed systems. A plurality of methods for logical address allocation are disclosed, which the network adapts based on the configurable parameters and the network working environment. Since the nodes are allocated logical address based on the algorithm, while routing the data packet each node calculates the shortest path next hop towards the destination based on the algorithm used for addressing and forward the data.

Claims

1. A method for allocating logical address optimally to a device at the time of network association with a wireless communication network system, comprising the steps of:

calculating the optimum number of router nodes required at any depth ‘

n’

by personal area network controller (PC) based on the configurable parameter ‘

margin’

, ‘

network directionality’ and

‘

directionality factor’

of the network to cover the area fully;

developing a logical address allocation algorithm based on the value of said optimum number of router nodes required at any depth (n) and configurable parameters which includes number of end device (C_m) a router node can have as its child, the number of depth after which again each router node have the opportunity to have configurable number of router nodes as its child and network policy for allocating additional child router node address among the peer nodes;

calculating the number of router nodes and end device nodes said router node can have as its child, based on said address allocation algorithm;

calculating the area, said router node needs to cover, based on neighboring nodes location and its capability information;

receiving beacon frame from all its neighboring router nodes and building neighbor table by unassociated node, wherein neighbor table contains all the information transmitted in beacon frame and required for association procedure along with its approximate distance from said unassociated node;

transmitting an association request by said unassociated nodes containing said neighbor table information to one of said neighboring router node based on its preference which includes signal strength of received beacon, personal area network identity and depth of said router node;

accumulating all the association requests and then processing it by said router node to calculate its approximate location based on the said neighbor table information transmitted as part of association request by said unassociated nodes and said router node'"'"'s own neighbor table information;

finding out number of full function device unassociated nodes said router node can have as its child router nodes within the margin which are relatively equidistant from the neighboring router nodes i.e. it forms the network relatively homogeneous than other possible nodes; and

associating said full function device unassociated nodes which are relatively equidistant from neighboring router nodes as its child router nodes and associating other nodes as its child end device nodes,

whereby the network uses the address in optimum manner and enables the network to grow longer, also the data routing is faster since the address is allocated based on the formula, the shortest path can be calculated based on the address allocation formula.

2. The method as claimed in claim 1, wherein calculating said optimum number of router nodes at any depth ‘

n’

to cover the area fully comprises the steps of;

calculating the area covered by said router node at its child node'"'"'s depth based on configurable parameters; and

dividing the total area at child node'"'"'s depth calculated based on “

network directionality” and

directionality factor”

of said network by said area covered by said router node,

whereby optimum number of router nodes required at any depth to cover the desired area fully is obtained.

3. The method as claimed in claim 1, wherein on every unsuccessful event of said finding out full function device unassociated nodes within the margin, said router node checks margin range closer by margin to find out full function device unassociated node.

4. The method as claimed in claim 2, wherein said area which is covered by said router node at its child node'"'"'s depth is calculated based on factors comprising:

depth of said router node from the personal area network controller; and

margin, which is a configurable percent of said router node'"'"'s transmission range in which router node prefers its child router node.

5. The method as claimed in claim 2, wherein said total area to cover at child node'"'"'s depth is calculated based on factors comprising:

network directionality, which is a configurable parameter to indicate the directionality of network growth, which includes for uni-directional network (=1), bi-directional network (=2) and so on, for omni-directional network said network directionality is equal to directionality factor of the network; and

directionality factor, which is a configurable parameter which allows user to divide the omni-directional network into that many number of factors.

6. The method as claimed in claim 2, wherein said optimum number of router nodes required covering the desired area fully, is directly proportional to said depth of the router node and network directionality.

7. The method as claimed in claim 2, wherein said optimum number of router nodes required covering the desired area fully is inversely proportional to said margin and directionality factor of the network.

8. The method as claimed in claim 1, wherein developing logical address allocation algorithm is comprising the steps of:

ascertaining depth, sector and term of said associating node (i.e. the unassociated node), which is trying to associate with the network;

allocating logical address to said associating node based on the depth of said associating node;

allocating logical address to said associating node based on the sector of said associating node;

allocating logical address to said associating node based on the term of said associating node;

allocating logical address to said associating node based on said number of end devices a router node can have as its child;

allocating logical address to said associating node based on the configurable parameter network periodicity i.e. the depth after which each router node gets the opportunity to have configurable number of router nodes as its child; and

allocating logical address to said associating node based on the configurable network policy according to which the additional child router node address is allocated among the peer nodes;

whereby said associating node logical address is equal to address consumed till previous depth plus address consumed till previous sector at current depth plus address consumed till previous term at current depth plus said term of associating node plus end device factor, where end device factor is null for router nodes and for end device it is equal to the number of associated end devices.

9. The method as claimed in claim 1, wherein said depth is the number of hops away from the personal area network controller (PC) of the wireless communication network.

10. The method as claimed in claim 8, wherein said sector signifies the branch detail of the network which originates from the router node directly associated with said personal area network controller (PC).

11. The method as claimed in claim 8, wherein said term signifies the position of said node with respect to its peer nodes associated with the same parent node.

12. The method as claimed in claim 8, wherein depth of said associating node is equal to the router node depth plus 1, where the router node is the node which is allowing said associating node to associate with it.

13. The method as claimed in claim 8, wherein sector of said associating node is equal to sector of the router node.

14. The method as claimed in claim 8, wherein term of said associating node depends on term of the router node and network policy for allocating term value for additional addresses of child nodes.

18. A method for routing data packet through shortest path in a wireless communication network system, where the address allocation algorithm is based on claim 1, comprising the steps of:

data packet generator node specifying the depth, sector, term and destination address information in data packet;

on reception of said data packet, current node which received said data packet ascertaining the depth, sector and term information of the destination location of said data packet, in case the depth, sector and term information is not readily available, said current node calculating it based on network configuration;

based on destination node'"'"'s depth, destination node'"'"'s sector, destination node'"'"'s term, said current node'"'"'s depth, current node'"'"'s sector, current node'"'"'s term, network directionality and directionality factor, said current node calculating the approximate direction of the destination node;

said current node finding out the next hop node nearest to the destination node based on information in its neighbor table about the neighboring node and said approximate direction of the destination node; and

said current node applying said next hop node as destination address in medium access control (MAC) header and transmitting said data packet;

whereby any data packet reaches its destination in minimum hops.

19. The method as claimed in claim 18, wherein said depth (d) of said destination node in said wireless communication network system is ascertained by satisfying the inequality given below:

k*((C_m+1)*S_d-2+R_d-1)<

A≦

k*((C_m+1)*S_d-1+R_d)

where A is said destination node address, d is said depth of destination node, k is number of sectors in said network, C_m is maximum number of child end device any router node or personal area network controller can have as its child, p is said network periodicity after which router node can have configured number of child router nodes as its child, wherein nodes are configured to have two child router nodes after p layers, R_d stands for number of router nodes at depth d, and S_d stands for number of router node till depth d in a sector,

20. The method as claimed in claim 19, wherein number of sectors (k) in said wireless communication network is ascertained using formula given below:

21. The method as claimed in claim 18, wherein said sector of said destination node in said wireless communication network system as is ascertained using formula given below:

22. The method as claimed in claim 18, wherein said term of said destination node in said wireless communication network system is ascertained using formula given below:

23. The method as claimed in claim 18, wherein logical address of router node having depth d, sector s and term t are ascertained using formula below:

Address=k*[(C_m+1)*S_d-2+R_d-1]+(s−

1)*(R_d+C_m*R_d-1)+t

where k is said number of sectors in the wireless communication network, s is sector of said destination node, C_m is maximum number of child end device any router node or personal area network controller can have as its child, R_d stands for said number of router nodes at depth d, and S_d stands for said number of router node till depth d.

24. The method as claimed in claim 18, wherein starting of logical address of end device of any router node, whose depth is d, sector is s and term is t is ascertained using formula below:

CEDA=k*[(C_m+1)*S_cd-2+R_cd-1]+(cs−

1)*(R_cd+C_m*R_cd-1)+R_cd-1)+R_cd+(t−

1)*C_m+1

where cd is child depth i.e. cd=d+1, cs is child sector i.e. cs=s, ct is child term, k is said number of sectors in the wireless communication network, s is sector of said destination node, C_m is maximum number of child end device any router node or personal area network controller can have as its child, R_d stands for said number of router nodes at depth d, and S_d stands for said number of router node till depth d.

26. A system for networking a wireless communication device having networking capabilities with a wireless communication network as claimed in claim 1 comprising:

a full function device personal area network controller (PC);

a reduced function device end device (ED);

means for calculating the optimum number of router nodes required at any depth ‘

n’

by personal area network controller (PC) based on the configurable parameter ‘

margin’

, ‘

network directionality’ and

‘

directionality factor’

of the network to cover the area fully;

means for developing an logical address allocation algorithm based on the value of said optimum number of router nodes required at any depth (n) and configurable parameters which includes number of end device (C_m) a router node can have as its child, the number of depth after which again each router node have the opportunity to have configurable number of router nodes as its child and network policy for allocating additional child router node address among the peer nodes;

means for calculating the number of router nodes and end device nodes said router node can have as its child, based on said address allocation algorithm;

means for calculating the area, said router node needs to cover, based on neighboring nodes location and its capability information;

means for receiving beacon frame from all its neighboring router nodes and building neighbor table by unassociated node, wherein neighbor table contains all the information transmitted in beacon frame and required for association procedure along with its approximate distance from said unassociated node using received signal strength;

means for transmitting an association request by unassociated nodes containing said neighbor table information to one of said neighboring router node based on its preference which includes signal strength of received beacon, personal area network identity and depth of said router node;

means for accumulating all the association requests and then processing it by router node to calculate its approximate location based on the said neighbor table information transmitted as part of association request by said unassociated nodes and said router node'"'"'s own neighbor table information;

means for finding out number of full function device unassociated nodes said router node can have as its child router nodes within the margin which are relatively equidistant from the neighboring router nodes i.e. it forms the network relatively homogeneous than other possible nodes; and

means for associating said full function device unassociated nodes which are relatively equidistant from neighboring router nodes as its child router nodes and associating other nodes as its child end device nodes,

whereby the network uses the address in optimum manner and enables the network to grow longer, also the data routing is faster since the address is allocated based on the formula, the shortest path can be calculated based on the address allocation formula.

27. The system as claimed in claim 26 comprising a full function device personal area network controller, a full function device router node and a reduced function device end device.

28. The system as claimed in claim 26, wherein said full function device is a wireless networking device capable of networking with reduced function device or other full function device and it is capable to operate in three modes serving as personal area network controller (PC), a router node (RN) or as an end device (ED).

29. The system as claimed in claim 26, wherein said reduced function device is a wireless networking device capable of networking with only full function device and it can serve as end device (ED) in any network.

15. A method for allocating logical address optimally to a device at the time of network association with a wireless communication network system, comprising the steps of:

configuring the full function device with the prior information of network growth beyond it for reserving the logical addresses, for case where user has no prior information of network growth beyond said full function device, the full function device is configured accordingly to indicate that it has no prior information about the network growth;

receiving beacon frame from all its neighboring router nodes and building neighbor table by unassociated node, wherein neighbor table contains all the information transmitted in beacon frame and required for association procedure along with its approximate distance from said unassociated node;

transmitting the association request by unassociated nodes as part of its association procedure, association request containing the information about its said logical address requirement, which is said configured value for full function device and null for reduced function device;

accumulating the association request for configurable period (T<sub>ASSOC—

RES</sub>) by said router nodes and then adding the address requirements of each said association request to get the total address requirement;

checking the available logical addresses for distribution by said router nodes, whether all the association requests requirement can be fulfilled;

allocating the requested number of logical addresses to the associating nodes which have specified their requirements, provided said router node has sufficient availability of logical addresses;

alternatively, in case said router node does not have sufficient availability of logical addresses to meet all the requests, taking address reallocation mechanism (ARM), which on success said router node allocating the logical addresses as per request in said association requests, otherwise allocating the available logical addresses proportionally based on requested values in said association requests and availability of logical addresses with said router node;

allocating the logical addresses to said unassociated nodes based on network configurable parameters, node'"'"'s depth and availability of logical addresses where said unassociated nodes have not specified its logical address requirement in said association request; and

propagating the network configurable parameters by said router node to all associating nodes,

whereby the logical address is allocated based on the associating node'"'"'s requirement and network configurable parameters which prudently uses the available logical address and thus improves the chance of all the unassociated node getting associated with the network.

16. The method for allocating logical addresses as claimed in claim 15, wherein said address reallocation mechanism (ARM) comprises the steps of:

said router node requesting its parent node for additional logical address requirement;

in case of availability of requested number of addresses, said router node'"'"'s parent node allocating the required logical addresses, otherwise taking said address reallocation mechanism (ARM) with its parent node, this recursive step can span up to preconfigured depth or by default up to personal area network controller (PC); and

said parent node responding to said router node about the newly allocated addresses,

whereby logical addresses are reallocated.

17. The method for allocating logical addresses as claimed in claim 15, wherein said address reallocation mechanism (ARM) comprises the steps of:

said router node requesting its neighboring node for additional logical address requirement;

in case of availability of requested number of addresses, said router node'"'"'s neighboring node allocating the required logical addresses, otherwise taking said address reallocation mechanism (ARM) with its neighboring or parent node based on configuration, this recursive step can span up to preconfigured depth or by default up to personal area network controller (PC);

said neighboring node responding to said router node about the allocated new addresses;

said neighboring node informing its parent node about said distribution of its logical address; and

said router node informing its parent node about said reallocation of logical address,

whereby logical addresses are reallocated.

25. A method for routing data packet through shortest path in a wireless communication network system, where the address allocation algorithm is based on claim 15, comprising the steps of:

on reception of data packet, node which received said data packet finding out the destination address from the data packet;

said node finding out the next hop node nearest to the destination node based on information in its neighbor table about the neighboring node logical address range and destination address;

in case said node does not find any neighboring node having destination address in its logical address range, said node applying next hop node as its parent node; and

said node applying said next hop node as destination address in medium access control (MAC) header and transmitting said data packet,

whereby any data packet will reach its destination in minimum hops.