Packet relay system and wireless node

• US 20100195560A1
• Filed: 11/24/2009
• Published: 08/05/2010
• Est. Priority Date: 01/30/2009
• Status: Active Grant

• Current Assignee: OKI Electric Industry Company Limited
• Original Assignee: OKI Electric Industry Company Limited
• Inventors: Yanagihara, Kentarou, Kubo, Yuki, Nozaki, Masanori
• Granted Patent: US 9,450,668 B2
• Time in Patent Office: Days
• US Class Current: 370/315
• CPC Class Codes: H04B 7/155 Ground-based stations H04B7/204 takes precedence
• CPC Class Codes: H04B 7/2606 Arrangements for base station coverage control, e.g. by using relays in tunnels

Abstract

A packet relay system in which each node calculates a link cost of each adjacent node based on an arrival rate of a packet from each adjacent node, acquires an accumulated value of a link cost calculated by each node in a range of nodes from a sink node for each adjacent node, calculates, for each adjacent node, a path cost of the one adjacent node by adding the link cost calculated to the accumulated value, and relays a data packet to one adjacent node selected from among nodes adjacent to the node based on a path cost of each adjacent node. This enables establishment of an upstream path to a sink node without increasing the amount of communication in a network.

Claims

1. A packet relay system including a plurality of nodes which relay a data packet to each other, each of the nodes including:

an arrival rate calculation unit which calculates an arrival rate of a packet from each node adjacent to the node among the plurality of nodes;

a link cost calculation unit which calculates a link cost of each adjacent node based on the arrival rate for each adjacent node;

an accumulated link cost value acquisition unit which acquires, for each adjacent node, an accumulated value of a link cost calculated by each node in a range of nodes from a sink node to each adjacent node among the plurality of nodes;

a path cost calculation unit which calculates, for each adjacent node, a path cost by adding the link cost calculated to the accumulated value; and

a packet relay unit which relays the data packet to one adjacent node selected from among nodes adjacent to the node based on the path cost of each adjacent node.

2. The packet relay system according to claim 1, wherein the packet relay unit relays the data packet to the one adjacent node corresponding to a lowest path cost among path costs of the adjacent nodes.

3. The packet relay system according to claim 2, wherein, when it is determined that relay of the data packet to the one adjacent node is not possible, the packet relay unit relays the data packet to another adjacent node corresponding to a path cost that is next lowest relative to the lowest path cost of the one adjacent node.

4. The packet relay system according to claim 1 is a wireless relay network system in which each of the plurality of nodes relays the data packet through a wireless communication path.

5. A packet relay system including a plurality of nodes configured in a tree format, each of the nodes including:

a packet hold unit which holds a packet from one of nodes adjacent to the node among the plurality of nodes until a predetermined transmission time is reached;

an aggregate packet generation unit which generates, when a packet is received from an adjacent node other than the one adjacent node until the transmission time is reached, an aggregate packet including an address list obtained by aggregating an address of the node, an address included in the packet held by the packet hold unit, and an address included in the received packet; and

an aggregate packet relay unit which relays the aggregate packet to an adjacent node that is located at an uppermost node position among the adjacent nodes as the transmission time is reached.

6. The packet relay system according to claim 5, wherein a packet generated by incorporating, as the address list, a set of address groups, each corresponding to a node group including a parent node corresponding to one of the plurality of addresses and a child node of the parent node, is used as the aggregate packet.

7. The packet relay system according to claim 5 is a wireless relay network system in which each of the plurality of nodes relays the data packet through a wireless communication path.

8. A packet relay system including a plurality of nodes which relay a data packet to each other, each of the nodes including:

a 2-hop adjacent node address acquisition unit which acquires, addresses of nodes adjacent to the node among the plurality of nodes, and addresses of second hop adjacent nodes adjacent to each of the adjacent nodes;

a 2-hop adjacent node address storage unit which stores, for each of the second hop adjacent nodes, the address of each of the second hop adjacent nodes and the address of each of the adjacent nodes to the node which have a relationship corresponding to each other;

a packet relay unit which relays, when it is determined that relay of the data packet, which is a packet to be transmitted to one second hop adjacent node adjacent to a first adjacent node of the adjacent nodes, to the first adjacent node is not possible, the data packet to an address of a second adjacent node among the adjacent nodes corresponding to addresses of the first adjacent node and the one second hop adjacent node in accordance with the address corresponding relationship stored in the 2-hop adjacent node address storage unit.

9. The packet relay system according to claim 8, wherein the node further includes:

an arrival rate calculation unit which calculates an arrival rate of a packet from each of the adjacent nodes; and

a link cost calculation unit which calculates a link cost of each of the adjacent nodes based on the arrival rate,

wherein the packet relay unit relays, when it is determined that relay of the data packet to the first adjacent nodes is not possible, the data packet to the address of the second adjacent node whose link cost is lowest among addresses of the adjacent nodes corresponding to addresses of the first adjacent node and the one second hop adjacent node in accordance with the address corresponding relationship stored in the 2-hop adjacent node address storage unit.

10. The packet relay system according to claim 8 is a wireless relay network system in which each of the plurality of nodes relays the data packet through a wireless communication path.

11. A wireless node for relaying a data packet through a wireless communication path, the node comprising:

an arrival rate calculation unit which calculates an arrival rate of a packet from each node adjacent to the node;

a link cost calculation unit which calculates a link cost of each adjacent node based on the arrival rate for each adjacent node;

an accumulated link cost value acquisition unit which acquires, for each adjacent node, an accumulated value of a link cost calculated by each node in a range of nodes from a sink node to each adjacent node;

a path cost calculation unit which calculates, for each adjacent node, a path cost by adding the link cost calculated to the accumulated value; and

a packet relay unit which relays the data packet to one adjacent node selected from among nodes adjacent to the node based on the path cost of each adjacent node.

12. The wireless node according to claim 11, wherein the packet relay unit relays the data packet to the one adjacent node corresponding to a lowest path cost among path costs of nodes adjacent to the node.

13. The wireless node according to claim 12, wherein, when it is determined that relay of the data packet to the one adjacent node is not possible, the packet relay unit relays the data packet to another adjacent node corresponding to a path cost that is next lowest relative to the lowest path cost of the one adjacent node.

14. A wireless node for relaying a data packet through a wireless communication path configured in a tree format, the node comprising:

a packet hold unit which holds a packet from one of nodes adjacent to the node until a predetermined transmission time is reached;

an aggregate packet generation unit which generates, when a packet is received from an adjacent node other than the one adjacent node until the transmission time is reached, an aggregate packet including an address list obtained by aggregating an address of the node, an address included in the packet held by the packet hold unit, and an address included in the received packet; and

an aggregate packet relay unit which relays the aggregate packet to an adjacent node that is located at an uppermost node position among the adjacent nodes as the transmission time is reached.

15. The wireless node according to claim 14, wherein a packet generated by incorporating, as the address list, a set of address groups, each corresponding to a node group including a parent node corresponding to one of the plurality of addresses and a child node of the parent node, is used as the aggregate packet.

16. A wireless node for relaying a data packet through a wireless communication path, the node comprising:

a 2-hop adjacent node address acquisition unit which acquires, addresses of nodes adjacent to the node and addresses of second hop adjacent nodes adjacent to each of the adjacent nodes;

a 2-hop adjacent node address storage unit which stores, for each of the second hop adjacent nodes, the address of each of the second hop adjacent nodes and the address of each of the adjacent nodes to the node which have a relationship corresponding to each other;

a packet relay unit which relays, when it is determined that relay of the data packet, which is a packet to be transmitted to one second hop adjacent node adjacent to a first adjacent node of the adjacent nodes, to the first adjacent node is not possible, the data packet to an address of a second adjacent node among the adjacent nodes corresponding to addresses of the first adjacent node and the one second hop adjacent node in accordance with the address corresponding relationship stored in the 2-hop adjacent node address storage unit.

17. The wireless node according to claim 16, wherein the node further includes:

an arrival rate calculation unit which calculates an arrival rate of a packet from each of the adjacent nodes; and

a link cost calculation unit which calculates a link cost of each of the adjacent nodes based on the arrival rate,

wherein the packet relay unit relays, when it is determined that relay of the data packet to the first adjacent nodes is not possible, the data packet to the address of the second adjacent node whose link cost is lowest among addresses of the adjacent nodes corresponding to addresses of the first adjacent node and the one second hop adjacent node in accordance with the address corresponding relationship stored in the 2-hop adjacent node address storage unit.