US20030016650A1

US20030016650A1 - Method used to create multihop RF network based on a low performance 8 bit microcontroller

Info

Publication number: US20030016650A1
Application number: US09/682,070
Authority: US
Inventors: Felix Missel
Original assignee: Individual
Current assignee: Individual
Priority date: 2001-07-17
Filing date: 2001-07-17
Publication date: 2003-01-23
Also published as: US7006454B2; US20050135328A1

Abstract

This invention comprises a method to manage the routing in a multi-hop network. The hardware platform is an 8-bit micro-controller with additional peripherals. The data storage unit (118) is implemented by an external memory. This method uses four internal data buffers and an algorithm to manage them inside the micro-controller.

Description

BACKGROUND OF INVENTION

1. Field of Invention

This invention relates to data transmission over a multi-hop RF network using a low cost and low processing power 8-bit micro controller in order to overcome power limitations on the signal.

2. Discussion of Prior Art

A RF network is a group of nodes distributed in an irregular topography, everyone within the power area of the other nodes.

Communicating with a node through more than one node is known as a multiple-hop communication system.

In order to overcome the problems of the power limitations of the signal, some RF networks employ a net layer that improves the utilization of a method which is capable of send a message hopping through nodes until it reaches the destination node.

These methods use one of two ways for routing, and according to which one is used, the method is table based or dynamical routing based. Table based stores all the routing information in a data storage unit or DSU ( 118), when a node needs to send a message, uses the information stored in the DSU (118) in order to route the message. Dynamical routing based routes dynamically the messages, and does not need the DSU, but the messages present in the network are higher, when a node needs to send a message sends a broadcast in order to obtain the path to the destination node and then sends the message. Due to mobility, the table based methods must maintain the table. The maintenance is an algorithm that periodically updates the table. The utilization of high performance micro-controllers to manage the complex algorithm for routing has been widely used U.S. Pat. No. 5,682,379, so, in order to decrease the cost of the device used as node this invention is a method to communicate nodes within a multi-hop network using low performance 8-BMC (114).

So is well known, the low performance 8-bit micro-controllers have speed, memory and processing limitations, so it is hard to use for a RF multi-hop network application. Thus, the devices developed with this method have to be economical because of the low performance 8-bit micro-controller low cost.

SUMMARY OF INVENTION

This invention comprises a method to manage the routing in a multi-hop network.

The hardware platform is an 8-bit micro-controller with additional peripherals. The data storage unit ( 118) is implemented by an external memory.

This method uses four internal data buffers and an algorithm to manage them inside the micro-controller.

OBJECTS AND ADVANTAGES

Accordingly, several objects and advantages of the present invention are:

a) To provide a wireless multi hop network management with a single 8-bit micro-controller, suitable to the processing and memory limitations of a low processing power micro-controller.

b) To interface an external serial device with the multi hop network.

c) To achieve a low cost device.

d) To increase the network area, instead increasing the power of the signal.

BRIEF DESCRIPTION OF DRAWINGS

FIG. 1 shows the hardware architecture for a single node. [0017]
FIG. 2 shows the data architecture inside the micro-controller, and the flow of data. [0018]
FIG. 3 shows the internal architecture of the data storage unit. [0019]
FIG. 4 shows the fields inside the header. [0020]
FIG. 5 shows a normal message transmission on a multi-hop network. [0021]
FIG. 6 shows the algorithm of the request response functionality.[0022]

LIST OF REFERENCE NUMERALS IN DRAWINGS

[0023] 110 Antenna.
[0024] 112 Serial device.
[0025] 114 8-bit micro-controller.
[0026] 116 Radio frequency transceiver.
[0027] 118 Data storage unit.
[0028] 210 Serial device input buffer.
[0029] 212 Auxiliary buffer.
[0030] 214 Network input buffer.
[0031] 216 Serial device output buffer.
[0032] 218 Network output buffer.
[0033] 310 Configuration data.
[0034] 312 a 1 First node address in the table.
[0035] 12 a 2 Second node address in the table.3
[0036] 312 a 3 Third node address in the table.
[0037] 312 an N° node address in the table.
[0038] 410 Transmitter node address field.
[0039] 412 Receiver node address field.
[0040] 414 Sender node address field.
[0041] 416 Destination node address field.
[0042] 418 Length of the message field.
[0043] 420 Frame tag field.
[0044] 422 Request response field.
[0045] 424 Data string field.
[0046] 426 Cyclic redundancy check field.
[0047] 510 Sender node.
[0048] 512 Transmitter node.
[0049] 514 Receiver node.
[0050] 516 Destination node.
[0051] 518 Message.
[0052] 610 Flowchart start blocks.
[0053] 612, 618, 622 Flowchart decision blocks.
[0054] 614, 616, 620, 626, 628, 630 Flowchart process blocks.
[0055] 624 Flowchart end blocks.

DETAILED DESCRIPTION

Each node uses as basic components a micro-controller ([0056] 114), a RF transceiver (116), a DSU (118) and a hardwired interface to communicate a serial device or SD (112) like a computer to the RF network.
Each node has two interfaces; one interface is node to serial device, comprising an asynchronous data input an output, and its own buffers ([0057] 210 and 216). Another interface is a node to net, with an input buffer (214) and an output buffer (218).
The buffers are located internally in the 8-bit micro-controller ([0058] 114) as shown on FIG. 2. The flow of the information goes through the buffers according to the kind of message.
Each node has one DSU ([0059] 118), located externally out the micro-controller. This DSU stores the address table, comprised by many node addresses or NA (312 a 1, 312 a 2, 312 a 3, until 312 an, let be n addresses), and the configuration data or CD (310).
A header is the beginning of the message. The header contains fields, which are useful to send messages through a multi-hop network; these fields manage the flow of the message through the net. Therefore, in order to send a message through the multi-hop network, it is needed only four fields: sender node address ([0060] 414), transmitter node address (410), receiver node address (412) and destination node address (416).
The sender node address or SNA ([0061] 414) contains the address of the node that originates the message. The transmitter node address or TNA (410) contains the address of the node that is transmitting the message, this address changes when the message go through the net adopting the address of the n° hop. The receiver node address or RNA (412) contains the address of the node that is receiving the message from the n° hop, and will be the n+1° hop in the next hop. The destination node address or DNA (416) contains the address of the last node that receives the message.
Some kind of messages requires an answer from the destination node, therefore, the header must contain a field inside that indicates this condition, so there is a field named RR ([0062] 422).

ADDITIONAL EMBODIMENTS

There are fields in the header that are not mentioned, but its use is reserved to the medium access control layer. They are: length or L ([0063] 418), frame tag or FT (420), data string or DS (424) and cyclic redundancy check or CRC (426).

OPERATION OF THE INVENTION

A normal communication in a multi-hop network is as shown in FIG. 5. This scheme comprises a message hopping from node to node. A sender node or SN ([0064] 510), it sends the message at first. A transmitter node or TN (512), it is the n° hop and transmits the message to the n+1° hop. A receiver node or RN (514), which is the n+1° hop and receives the message in order to retransmit it; a destination node or DN (516), which receives the message at last; and a message or M (518), which is hopping through the network.
The operation of this invention comprises four cases, when the message goes from the serial device to the network, from the serial device to the same serial device, from the network to the serial device, and from the network to the network. [0065]
The cases where the message returns to the same way, let be the serial device or the network, are caused by network commands, and they are another kind of message that are intended to makes changes to the configuration data in the DSU ([0066] 118). Therefore, the message is replied by the node itself and the response is sent back to the sender, let be a node or the serial device.
When the message goes from the serial device to network, the data is received from the serial device and stored in a buffer named serial device input buffer or SDIB ([0067] 210), then the message is copied, previous processing, to a transmission buffer or network output buffer NOB (218), and goes away through the network.
When the message goes from the serial device to the same serial device, the data is received from the serial device and stored in the serial device input buffer or SDIB ([0068] 210), then the message is copied, previous processing, to a serial device output buffer or SDOB (216), and goes to the serial device (112).
When the message goes from the network to the serial device, the data is received from a buffer named network input buffer NIB ([0069] 214) and stored in a buffer named auxiliary buffer or AB (212), thus before processing, the message is copied, to the SDOB (216), and goes to the serial device (112).
When the message goes from the network to the network, the data is received from the NIB ([0070] 214), then is copied to the AB (212), thus before processing, the message is copied, to the NOB (218), and goes away through the network. This case can be originated by a retransmission of the message too.
In order to ensure the request response functionality, this invention enables the utilization of the algorithm shown in FIG. 6. [0071]
This algorithm works as follows. When a message is received from the network ([0072] 610), is compared the destination node address (416) with the own node address (612). If the comparison does not match, this is because a retransmission message, then the node searches for the next hop (614) and retransmit the message (616). When the comparison matches, the message is tested to determine if it is a network command or NC (618). If the message is a NC, the NC will be executed by the node (620). Then the RR (422) is tested (622), if the response is required the node sends a message back to the sender node (626), if no response is required the algorithm ends (624). When the message is not a NC, then the message is sent to the serial device (628). Then the RR (422) is tested (622), if the response is required the node sends a request response message to the serial device (630), thus after the serial device answer, the node sends this answer back to the sender node (626). If no response is required, then the algorithm ends (624).
The automatic creation of the table is the most important processes because the table once completed can accept few changes; one of these changes could be the arrival of a new node in the network. [0073]
In order to illustrate the algorithm of automatic creation of the table, let be a node surrounded by neighbors and all of them surrounded by distant neighbors. [0074]
A first node sends its update table to everybody, then the neighborhood send the acknowledge message to the sender, the sender sorts the neighborhood by its address, then the sender requires each by each neighborhood its node address table in order to complete the entire network. If a neighbor does not sends the acknowledge message, thus it will figure as a node behind one neighbor, then the error will disappear when these nodes exchange messages between them. Once the first node has the completed table, sends messages to the network, each by each node, in order to include the own address in the others node tables. [0075]

Conclusion, Ramification and Scope of Invention

This invention is suitable for developing low cost communication devices on a RF medium, because the use of low cost micro-controller and low cost transmitters. However, a device that uses this method can be easily connected to a serial device, for example: a computer, with a minimal of technical knowledge. Therefore, it is possible to make a low cost and reliable RF computer network, with low power consumption, ideally when powered with batteries. [0076]
The description above is intended, however, to include all such modifications and alterations insofar as they come within the scope of the appended claims or the equivalents thereof. [0077]

Claims

What is claimed is:

1. A method for managing the routing in a multi-hop network, the method comprising the steps of:

Having a node with a mircro-controller means, a RF transceiver means, data storage means, a network interface means with an input buffer, output buffer and auxiliary buffer and a serial device communication means;

Having the data storage means store a plurality of node addresses and configuration data;

Having a plurlarity of serial devices;

Having the messages contain a header at the beginning of the message with the fields sender node address, transmitter node address, receiver node address and destination node address;

Processing a message to a node from the serial device to network by receiving the message from the serial device, storing the message in the input buffer, copying the message to the output buffer, and transmitting the message to the the network;

Processing a message to a node from a serial device to the same serial device by receiving the message from the serial device, storing the message in the input buffer, copying the message is copied to the output buffer and transmitting the message to the serial device;

Processing a message to a node from the network to a serial by receiving the message from the input buffer, storing the message the auxiliary buffer, copying the message to the output buffer, and transmitting the message to the serial device;

Processing a message to a node from the network to the network by receiving the message from the input buffer, storing the message the auxiliary buffer, copying the message to the output buffer, and transmitting the message to the network;

Processing a message by having a sender node send the message, having a plurlarity of nodes receive and re-transmit the message until the destination node receives the message; and

Processing a message from the network to a node by comparing the node's address with the destination node address; if the address does not match, the message is a retransmission message and the node searches for the next node and retransmits the message, if the address matches, the message is tested to determine if the message is a network command, if the message is a network command, the network command will be executed by the node, if the message is not a network command, the message is sent to the serial device, if an acknowledgement is required the node sends a request response message to the serial device, after the node receives the acknowledgement from serial device the node sends an acknowledgement to the sender node.

2. The method of claim 1 in which said microcontroller means is an 8-bit micro-controller.

3. The method of claim 1 in which said network interface means consists of an input buffer and an output buffer located internal on the microcontroller means.

4. The method of claim 1 in which said header contains the fields sender node address, transmitter node address, receiver node address, destination node address, length, frame tag, data string and cyclic redundancy check.

5. The method of claim 1 in which said serial device is a computer,

6. The method of claim 1 in which said serial device is a DVC.

7. The method of claim 1 which includes the steps of:

setting up an address table automatically by a node send a message to all of the nodes on the network, having the nodes send acknowledge messages to the sender node, having the sender node sort the nodes by the nodes' addresses and loading the addresses into an address table, then the sender sends messages to each node in the network to include the sender node's address in the other node's address tables.

8. A communication system comprising: A node with a mircro-controller means, a RF transceiver means, data storage means, a network interface means with an input buffer, output buffer and anxiallary buffer and a serial device communication means;

A Data storage means store a plurality of node addresses and configuration data;

A plurlarity of serial devices;

Messages that contain a header at the beginning of the message with the fields sender node address, transmitter node address, receiver node address and destination node address;

Said node processing a message from the serial device to network by receiving the message from the serial device, storing the message in the input buffer, copying the message to the output buffer, and transmitting the message to the the network;

Said node processing a message from a serial device to the same serial by receiving the message from the serial device, storing the message in the input buffer, copying the message to the output buffer, and transmitting the message to the serial device;

Said node processing a message from the network to a the serial device by receiving the message an input buffer, storing the message on an auxiliary buffer, copying the message to the output buffer, and transmitting the message to the serial device;

Said node processing a message from the network to the network by receiving the message an input buffer, storing the message on an auxiliary buffer, copying the message to the output buffer, and transmitting the message to the network;

Said node processing a message by having a sender node sends the message at first, having a plurlarity of nodes receive and re-transmit the message until the destination node receives the message; and

Said node processing a message from the network in which the destination node address is compared with the node's address, if the address does not match, the message is a retransmission message and the node searches for the next node and retransmits the message, if the address matches, the message is tested to determine if the message is a network command, if the message is a network command, the network command will be executed by the node, if the message is not a network command, the message is sent to the serial device, if an acknowledgement is required the node sends a request response message to the serial device, after the node receives the acknowledgement from serial device the node sends an acknowledgement to the sender node.

9. The device of claim 8 in which said microcontroller means is an 8-bit microcontroller.

10. The device of claim 8 in which said network interface means consists of an input buffer and an output buffer located internal on the microcontroller means.

11. The device of claim 8 in which said header contains the fields sender node address, transmitter node address, receiver node address, destination node address, length, frame tag, data string and cyclic redundancy check.

12. The method of claim 8 in which said serial device is a computer

13. The method of claim 8 in which said serial device is a DVC.

14. The device of claim 8 in which an address table is set up automatically by a node sending a message to all of the nodes on the network, having the nodes send acknowledge messages to the sender node, having the sender node sort the nodes by the nodes' addresses and load into an address table, then the sender sends messages to each node in the network to include the sender node's address in the other nodes' address tables.