Abstract of Master's Thesis

Introduction

Actuality

Embedded systems have become a part of everyday life. We can see a process of rapid growth and continuous cost reduction in microprocessor technology. Automation of various processes, thereby, applies not only in production but also to everyday life. There are over 30 microcontroller based devices in each house, so their communication is an actual problem. Wired solutions are hard to apply in these conditions. Wireless networks have significant advantages like flexible architecture, ease of installation and ease of maintenance. [1]

There is a new class of wireless - short-range wireless networks. These networks have a number of features. The devices included in this network are small and use mostly battery power. These networks are the Ad-Hoc networks - highly specialized networks which do not rely on a preexisting infrastructure. In this regard there are numerous of problems connected with creation and functioning of these networks - adding and removing of the devices, authentication of the devices, an efficient routing, data security, network liveness, battery life of the end devices. [2]

Actuality of Master’s thesis is determined by the actuality of the wireless technologies. Major areas of the wireless communications deployment are wireless sensor networks used in industrial control systems and SCADA, as well as in everyday life in the form of home automation (Smart House). The market of these systems is growing every year, and that means the research of routing issues are highly relevant to interoperability improving.

Aims and Goals

The object of study is short-range wireless networks, including wireless sensor networks.

The subject of the study is the routing algorithms in networks based on IEEE 802.11.4.

The purpose of master's thesis is to study the effectiveness of routing algorithms in short range wireless networks in consideration of operation specifics. To achieve this goal we should:

• review and analyze the network stacks, which are based on IEEE 802.11.4;
• review and analyze the most common routing algorithms;
• review existing short-range wireless network simulators;
• choose the simulation environment;
• select criteria for comparing the effectiveness of different routing algorithms;
• simulate the routing algorithms;
• analyze simulation results and compare the routing algorithms on selected criteria;
• develop hardware and software for wireless network node;
• experiment with developed hardware;

In this study it is planned to experiment with modeling software, use statistical analysis of simulation results and make experimental studies with the developed hardware.

Scientific and practical novelty

The scientific novelty of the master's thesis consists in obtaining a method of comparing the effectiveness of various routing algorithms based on wireless network simulation.

The practical novelty is in using of this technique in selection of technology, network topology and routing algorithm during the design of short range wireless networks.

Approbation

The main results were reported on international scientific conferences for students, graduate students and young scientists "Information and computer technologies - 2009" (section "Design of computer and digital devices, FPGA-technology") and "Information control systems and computer monitoring - 2010" (section "Computer Engineering").

The high interest of conference participants to these presentations shows the actuality of the chosen topic. Reports were marked with highest rank in the section.

The main content

General information about ZigBee technology

Wireless short-range networks designed to connect microcontroller devices have been termed WPAN (Wireless Personal Area Network), a standard which has been developed by the IEEE 802.15 working group. This standard includes the specification for wireless handheld devices, Bluetooth (IEEE 802.15.1) and a set of high-level network protocols that use low-power radio transmitters - ZigBee (IEEE 802.15.4). Standards for ZigBee and Bluetooth use 2.4 GHz unlicensed frequency range but there are considerable differences in their characteristics which are presented in the table 1. [3]

ZigBee protocol was designed for maximum energy efficiency, which allows devices to be in sleep mode most of the time. ZigBee devices can operate for a year or even more off of one battery

ZigBee networks have self-generating and self-healing abilities. ZigBee technology can be used not only for simple connections like point-to-point and star, but also for the complex network topologies of tree and mesh.[4]

The size of ZigBee coverage area depends on several factors, but primarily on the sensitivity of the receiver and power of the transmitter. The distance between the nodes in an open space can reach hundreds of meters. In this case ZigBee network coverage area may be considerably wider than the distance between the nodes due to relaying.

Thus, the ZigBee network is a dynamic decentralized power efficient wireless network with the ability to relay messages, being a suitable technology for embedded systems communication. However, it must be taken into account that the WPAN networks operate in unlicensed frequency range. There may be interference from extraneous sources of radio signals in some cases. Decentralization, in turn, raises the problem of routing in data networks. It is desirable to avoid the retransmission of the same data, but in addition, bear in mind that devices can be inaccessible due to the lack of energy and external effects. In such cases the data exchange scheme must be modified.

In recent years a fairly large number of routing algorithms were developed. The best known ones are DSR (Dynamic source routing) and AODV (Ad-hoc on-demand Distance Vector routing). AODV was implemented in ZigBee / ZigBee PRO devices as the basic routing protocol. A special feature of AODV protocol is an implicit assumption that any node in the network can participate in routing. However, the ZigBee network is a heterogeneous network. Devices have different roles and functions: a coordinator, a router, a sleeping unit and the end device.

The coordinator manages the network, stores information about its topology and serves as a gateway for data collected throughout the wireless sensor network. Sensor networks typically use only one coordinator. Routers route packets over the network and must be ready to transfer data at any time. Therefore, these nodes do not use battery power. Sleeping and mobile devices use a low power mode and typically are battery-powered. Usually they serve as sensors or executive device control unit. [5]

Routing in ZigBee Networks

ZigBee uses the following methods of routing:

• broadcasting
• source routing
• mesh routing
• tree routing

Each of these methods has its advantages and disadvantages listed in Table 2

Broadcasting

Broadcasting allows one node send a packet to multiple nodes. The method does not use acknowledgment (delivery not guaranteed), and requires significant network resources. Broadcasting is the basis for building complex routes.

When a node initiates a broadcast, the message is relayed to all neighbor routers to a certain limit, as shown in Figure 1. Broadcast expands like ripples in a pond. Every node that receives a broadcast message adds a record in a special Broadcast Transaction Table (BTT) and reduces the value of the radius field. If the field reaches a radius of unity, further retransmission packet is not performed. BTT also prevents recurrent receiving for broadcast messages. In the BTT table timeout value is specified for each entry, which, coupled with the limited size of the table introduces a limit on the number of broadcast messages in a time unit. If the table is full, the broadcast message will not be accepted.

Broadcast messages are distributed very slowly and lead to heavy network load so their use should be restricted. Note that only coordinators and routers may participate in the relay.

Source routing

In source routing the path of packet is determined by its sender. With strict source routing the packet header contains its full path; with loose source routing path is contained partially.

Source routing is expensive for wireless transmission. Package size for IEEE 802.15.4 physical layer is limited to 127 bytes. Taking into account the overhead of the ZigBee payload is about 100 bytes. If the source routing is used and the route is long, the payload can be reduced up to 60 bytes. Source routing is present in ZigBee, but the length of the route is limited to five hops to minimize overhead.

Mesh

The mesh network is a simple and flexible technology. The route lies from one node to another and passes through any number of intermediate nodes. If something happens to the route (node becomes unavailable or some obstruction for the signal appears), the new route is calculated automatically. Unlike broadcasting, the mesh uses only nodes that are included in the route, which significantly reduces the network load and speeds up the transfer. Also, the sending host knows for sure whether the message is delivered.

Routing is based on popular Advanced Ad-hoc On-Demand Distance Vectoring (AODV) algorithm for dynamic routing. This algorithm does not impose strict requirements for memory (ZigBee devices usually have no more than 4KB of RAM). In AODV algorithm route information is distributed - each node in the network contains a routing table, which stores records of neighboring nodes on the route. The routing table can contain several dozen of values. Routes are usually unidirectional and exist till can be used. In case of the route failure the sender node is informed to find a new route. It should be noted that in this algorithm, the network is a weighted graph. A signal quality between nodes is used as the weights of line of the graph. The sum of weights of the line is stored in the package header.

Initially the original mesh does not contain any information about routes. Determining the route begins with a broadcast message from the sender node. For example, in Figure 2, node 1 sends a packet to node 10. Node 10 is not a neighbor of node 1, and the route is unknown so the route search begins. The message is broadcasted to all nodes and at each node weight of the line of the graph is added to packet header. It should be noted that the longer route with a higher connection quality is preferable, because the retransmission of the missing packet will take longer than the passing of extra node in the route. [6]

For simplicity we take equal weights of lines in the graph. Thus, we have the shortest path from node 1 to node 5, and then to node 10. Node 10 waits for some time, until it receives all messages. Message with minimal weight sum is chosen. Then node 10 makes a response to the initial node, as shown in Figure 3. Nodes 5 and 1 now have appropriate entry in their routing table. Other nodes delete their records on timeout.

It should be noted that ZigBee is not actively seeking for the most optimal route. An established route will be kept as long as it is in working condition. However, you can regularly update routing information by the software. Please keep in mind that the route search can take several seconds.

Tree routing

This type of routing is used together with a special method of network nodes addressing. It should be noted that the ZigBee network nodes have multiple IP addresses – the MAC address, assigned by the manufacturer (64 bits) and the short network address (16 bits). The use of short addresses can reduce the header size, as the packet must hold both the sender’s and the receiver’s addresses.

In the case of Cskip (child skip) addressing the network coordinator has the default zero address. Each new node, connected to the network, receives an address from the parent node, which depends on a new node type (router or end device). Cskip uses three parameters to determine the address - maxDepth (maximum depth of the tree), maxChildren (maximum number of children connected to node) and maxRouters (the maximum number of routers).

Coordinator (zero node) is a root of formed symmetrical tree. All routers connected to the coordinator are the first level of the tree, and the routers connected to them are the second, etc. The first router connected to the coordinator receives an address of 0x0001. The second one receives the address large enough all the possible children in the tree formed by the first router could be numbered. Example of addressing and the network settings are shown in Figure 3.

Among the limitations are the static topology organization and general unreliability of the network. With the destruction of only one link whole branch of a tree will be isolated and the integrity of the network will be broken. [7]

The hardware implementation of a network node

To implement ZigBee node we will use Atmel ATmega32 AVR microcontroller and Chipcon CC2500 transceiver. The block diagram is shown in Figure 4. These microchips are widely-distributed and have a low cost, which allows their use in low-cost embedded systems. [8]

AVR controllers use a scalar RISC architecture that provides 20MIPS at a frequency of approximately 20MHz. This computing power should be sufficient for coordinators and routers. Embedded peripherals (PWM, UART and ADC) can be used to connect the operation units and sensors on the target devices. The presence of energy-saving features allows using the controller in battery-powered modules. That means all the elements of heterogeneous ZigBee network can be implemented with the same hardware, reducing development time and cheapening the final device. [10]

Chipcon CC2500 chip is designed for low-power wireless devices in 2.4 GHz frequency band and has a low cost. This transceiver requires a minimum of external components, which greatly simplifies a development. The chip is clocked by crystal oscillator Q2 with a frequency in the range of 26-27 MHz. Precision crystal oscillator must be uses as an element with the significant impact on the transceiver’s frequency. Alternatively the frequency of the transceiver can be changed with built-in adjustment.

CC2500 is very sensitive to the quality of power supply. The change of supply voltage during transmitting or receiving leads to the frequency change. LF33 or KA7805 stabilization circuits with additional capacitors are used.

PC communication is organized using microcontroller’s UART pins connected to the COM port via MAX232 logic level translator. ZigBee transceiver CC2500 is connected to the serial peripheral interface SPI. The data between ZigBee modules are transmitted in 64 bytes packets with parity.

Conclusion

The main types of routing in ZigBee network were reviewed in this paper. A comparative analysis of different types of routing was made. Various types of routing can be used depending on conditions, but the optimal type of network topology is a mesh using mesh routing algorithms. It is resistant to link rupture, is optimal for speed and does not does not impose strict requirements to the hardware. Routing algorithms used for the organization of this type of topology should be further studied and improved.

References

1. Материалы альянса ZigBee / Интернет ресурс. — Режим доступа: www.zigbee.org
2. Patrick Kinney. ZigBee Technology: Wireless Control that Simply Works / Kinney Consulting LLC, Chair of IEEE 802.15.4 Task Group, 2003 / Интернет ресурс. — Режим доступа: http://intranet.daiict.ac.in/~ranjan/sn/papers/Zigbee.pdf
3. F. L. Lewis. Wireless Sensor Networks / Automation and Robotics Research Institute, The University of Texas at Arlington / Интернет ресурс. — Режим доступа: http://arri.uta.edu/acs/networks/WirelessSensorNetChap04.pdf
4. Kemal Akkaya and Mohamed Younis. A Survey on Routing Protocols for Wireless Sensor Networks / Department of Computer Science and Electrical Engineering, University of Maryland, Baltimore County / Интернет ресурс. — Режим доступа: http://www.cs.umbc.edu/~kemal1/mypapers/Akkaya_Younis_JoAdHocRevised.pdf
5. Curt Schurgers,Mani B. Srivastava. Energy Efficient Routing in Wireless Sensor Networks / Networked & Embedded Systems Lab (NESL), University of California at Los Angeles / Интернет ресурс. — Режим доступа: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.4476
6. Ian D. Chakeres, Elizabeth M. Belding-Royer. AODV Routing Protocol Implementation Design / Dept. of Electrical & Computer Engineering, University of California, Santa Barbara / Интернет ресурс. — Режим доступа: http://moment.cs.ucsb.edu/pub/wwan_chakeres_i.pdf
7. Drew Gislason. ZigBee Wireless Networking. — Newnes, 2008
8. Shahin Farahani. ZigBee Wireless Networks and Transceivers. — Newnes, 2008
9. Панфилов Д., Соколов М. Введение в беспроводную технологию ZigBee стандарта 802.15.4
   Электронные компоненты. — Киев, 2004. — №12(73). — С.73-79
10. Шатунов М. Штрапенин Г. Интеграция технологии ZigBee в электронные устройства:
    Компоненты и технологии. — Минск, 2005. — №10(130). — С.130-134