Paper—A Routing Algorithm Based on Zigbee Technology
A Routing Algorithm Based on Zigbee Technology
[Link]
Xieji Gang
Nanjing Institute Of Industry Technology, Jiangsu, China
xiejigang294812@[Link]
Abstract—To realize the exploration of A routing algorithm for ZigBee tech-
nology, a kind of intelligent parking system based on ZigBee wireless sensor net-
work is designed, and the parking space is managed by online and offline inter-
action. First of all, the status of parking at home and abroad is studied, and the
demand for parking is analyzed. Secondly, the intelligent scheme of parking sys-
tem is studied, including parking guidance technology and parking space intelli-
gent recommendation technology. The former is based on the A routing algorithm
to search the shortest path, and uses Unity for route planning simulation, and the
latter is based on collaboration filtering algorithm to discuss the recommendation
method of similar parking spaces. The result shows that the prototype of an in-
telligent parking system based on ZigBee is eventually realized, and the functions
of online viewing, online parking reservation, online path planning and parking
guidance are realized. As a result, the purpose of managing offline parking spaces
through online is achieved, the utilization rate of resources in the existing parking
lot is improved and the use rate of parking space is promoted. At last, it effec-
tively alleviates the urban parking chaos and has certain application value.
Keywords—ZigBee, intelligent parking, A routing algorithm, Internet of things
(IoT)
1 Introduction
Since the twenty-first Century, the level of the national economy has been greatly
improved, the process of urbanization has been promoted, and the population has been
increased. As a result, these lead to the emergence of a series of urban problems, among
which the most prominent is the urban traffic problem. On the one hand, people's living
standards are getting higher and higher, the number of urban private vehicles increase
rapidly, and the demand for corresponding traffic facilities is increasing. On the other
hand, the construction speed of urban roads and parking lots is relatively slow, causing
traffic jam, environmental pollution, parking difficulty and difficulty in traveling. The
contradiction between the increasing demand for parking and the number of parking
lots provided by the city is becoming more and more prominent, and parking problem
has become the bottleneck of the sustainable development of urban traffic.
With the rapid economic development, people's living standards are improved, and
the "vehicle family" group is becoming larger and larger. However, when the vehicle
brings convenience to people's life, it also causes a considerable number of problems,
90 [Link]
Paper—A Routing Algorithm Based on Zigbee Technology
in which the parking disorder and parking difficulty have become the prominent con-
tradiction in the process of urban development. In 2016, several relevant departments
of the state jointly issued The Notice on Further Improving the Planning and Construc-
tion of Urban Parking Lot and the Policy of Land Use. It encourages social capital to
participate in the parking industry, fully digs and utilizes the ground and underground
space, and promotes the multi-functional three-dimensional development and com-
pound utilization of the construction land. The intelligent parking service based on
multi-functional three-dimensional development and compound utilization will usher
in a great opportunity for development. A large number of vehicles have worsened the
city's traffic conditions and traffic accidents are occurring frequently. In the meanwhile,
a large number of automobile exhaust emissions seriously pollute the quality of the
city's air. To solve these problems, the government implements the administrative pol-
icy of odd-and-even license plate rule to reduce the pressure and air pollution of the
urban traffic system. But this only solves the problem on the surface. In order to solve
the problem fundamentally, it is necessary to speed up the construction of urban traffic,
combine the new technology and new concept, vehiclery out intelligent management,
and rationally plan the urban traffic.
Therefore, it is urgent to develop and design a complete intelligent parking manage-
ment system to meet the requirements of effective parking management at present. The
intelligent parking management system uses highly automated management equipment,
combined with computer network, wireless communication technology and Internet
technology to manage the parking lot in real time and efficiently. It is necessary to study
and establish an intelligent management system of parking lot to realize automatic park-
ing system with advanced technology, control optimization, efficient operation of
equipment and centralized management. At the same time, the intelligent parking man-
agement system has become the supporting facility for a great number of large and
medium-sized comprehensive commercial buildings, schools and residential commu-
nities.
2 Literature review
In the early days, the equipment used in location estimation was compass. In the last
century, with the continuous maturity and rapid development of electronic communi-
cation technology, many large-scale wireless location systems have been developed.
The global positioning system (GPS) is a new generation of space satellite navigation
and positioning system developed by the United States in 1970s, mainly used for mili-
tary purposes. So far, GPS system has gradually entered people's daily life, and GPS
navigation mobile phone and vehicle GPS navigator can be seen everywhere, which is
convenient for people to know their position whenever and anywhere when they are
travelling.
The researchers envisaged the integration of remote wireless mobile communication
technology and used the advantages to establish a remote wireless monitoring network
with strong expansibility, flexible networking and safe and reliable network. Choe et
al. (2017) designed a real-time and dynamic parking guidance system to monitor the
iJOE ‒ Vol. 14, No. 11, 2018 91
Paper—A Routing Algorithm Based on Zigbee Technology
main parking area, collect the data through the computer controlling the underlying
system. The information of the parking lot and the road condition are displayed on the
variable electronic road signs, and the rest of the parking space in the surrounding park-
ing lot is updated in real time. The owner of the vehicle chooses the parking lot based
on the electronic indicator [1]. Vlahogianni et al. (2016) used the operator's parking
guidance and information system, adopted three levels of guidance and display in the
district, the intersection and the parking lot to locate the parking lot and the driving
direction of the parking vehicle, and update the number of remaining parking space of
the parking lot to facilitate the user to choose the parking [2]. Liu et al. (2017) proposed
a city intelligent parking system based on Client/Server mode based on Android system.
On the basis of location based service, unified management is conducted for the system,
which has intelligent parking, intelligent charging, and log records functions [3]. Song
et al. (2017) proposed an intelligent parking lot lot navigation scheme based on the
ZigBee technology of the Internet of things (IoT). It uses ZigBee and ultrasonic to deal
with the vehicle location detection function, and improves the parking efficiency by
modifying the shortest path algorithm [4]. Khan et al. (2016) studied wireless remote
monitoring based on wireless sensor network (WSN). The WSN composed of ZigBee
technology has the characteristics of simple structure, small size, and low cost. It can
realize close range wireless connection, which can ensure the real-time and reliability
of data transmission [5]. Khan et al. (2016), through the analysis of the new and open
wireless interconnection technology ZigBee technology, combined with sensor tech-
nology, ZigBee technology and routing protocol, constructed a WSN [6]. Moridi et al.
(2018) proposed a CC2431 chip and ZigBee WSN coal mine monitoring system based
on received signal strength indication (RSSI) wireless location algorithm. It was pro-
moted by the TI company, which has positioning and tracking engine and has good
reliability and real-time performance [7]. Han et al. (2016), aiming at the diversity of
the WSN application environment and irregularity effects on the deployment of sensor
nodes, a kind of indoor 3D scene reconstruction and 3D ray tracking method is pro-
posed. It can improve the efficiency and accuracy of ZigBee transmission modeling and
simulation in indoor environment and can be well used in different indoor environments
[8].
To sum up, the above research is mainly aimed at the integration of ZigBee technol-
ogy, wireless remote monitoring and system data acquisition, but in the selection of
methods, it is still deficient. Therefore, based on the above research status, the A routing
algorithm based on ZigBee technology is mainly studied, an intelligent parking system
based on ZigBee WSN is designed, and the parking space is managed through the online
and offline interaction.
3 Method
3.1 A routing algorithm
The A* search algorithm is essentially the best priority search algorithm with con-
straints, which is used to find the shortest path from a specified point to another in a
92 [Link]
Paper—A Routing Algorithm Based on Zigbee Technology
two-dimensional grid. Before using the A* search algorithm, it is necessary to simplify
the problem to a two-dimensional mesh.
If in a two-dimensional grid, A is the starting point and B is the end point, if a person
wants to go from A to B, how should he go? We do the following operations.
First, start from point A, and use it as a pending point to store in the "startup list".
Although there is only one element in the list, there will be more in the future. Your
path may pass through the grid it contains (or probably not) and it is just a list of check-
erboards.
Second, look for all grids accessible or passable around the starting point and skip
the mark of grids that cannot be passed through. Add them to the startup list and save
A as the "father grid" of all these grids.
Third, delete the point A from the startup list, add it to a "close list", and close the
grids that do not need to be checked again in the list. Next, choose the lowest nearest
neighbor grids in the list. Each heuristic search algorithm has an evaluation function.
The valuation function of the A* search algorithm is F=G+H, and G moves from the
starting point A to the generated path and moves to the moving cost of the specified
grid. H moves from the specified grid to the pre-estimated moving cost of the end point
B. Here, the square of the distance from the current lattice to the target lattice is calcu-
lated. To continue searching, the grids with the lowest F value are chosen from the
startup list. Then, the following treatment is vehicleried out to the selected grids.
Fourth, find the grids with the lowest F value, delete it from the startup list, and then
add it to the closed list.
Fifth, check all adjacent grids. If they are not in the startup list, add them to the
startup list. The new square is used as the selected square grid node. Skip those that are
already in or out of the list.
Sixth, if an adjacent grid is already in the startup list, check whether the current path
is better. In other words, check whether a lower G value can be obtained if a new path
is used to reach it. If not, don't do anything. If the new G value is lower, set the parent
node of the new grid to the currently selected grid. In this way, keep looking for a lower
F value and looking for the next lattice, until the B grid is added to the close list. From
the grid B, it searches for the parent node until the grid A, which is the shortest path
between A and B. If the B point is not added to the close list, the B point is not available.
3.2 Parking lot detection and control module
The ca position detection and control module is responsible for the data collection
and the hardware control. The data collected by the sensor is the data source of the
whole system, and the effective data can drive the system to work properly. The module
mainly consists of ultrasonic sensor, Arduino controller, ZigBee module and buzzer,
which together make up the vehicle position detection device and hardware control de-
vice, and build a typical sensing network. In this sensor network, the sensor is respon-
sible for detecting data, and the ZigBee network is responsible for communicating with
the upper layer, and the buzzer is used to respond to the user's operation of booking a
vehicle position.
iJOE ‒ Vol. 14, No. 11, 2018 93
Paper—A Routing Algorithm Based on Zigbee Technology
In practical applications, in extreme cases, a number of mandatory protection
measures can be triggered to prevent other users from entering the booked parking
space if the user books the parking space. In the parking detection and control module,
Arduino is responsible for coordinating each hardware work, and its data interaction is
shown in Figure 1.
Buzzer
Ultrasonic Arduino ZigBee routing
sensor controller module
ZigBee
Coordinator
Buzzer node
Ultrasonic Arduino ZigBee routing
sensor controller module
Fig. 1. Parking lot detection and control module structure diagram
Each parking node is controlled by a set of vehicle location detection and control
modules. When the status of the vehicle is changed, the sensing data is transmitted to
the ZigBee network through the Arduino controller and sent to the host computer serial
port. The upper computer submits the data to the upper layer application. In addition,
when the control information comes in, the host computer will broadcast the data to
each vehicle node through the ZigBee network, and the Arduino controller in the park-
ing lot node reads the control information through serial communication to judge
whether it is the target node of the information. If it is not, then discard the information;
otherwise, read the control information and control the buzzer working.
3.3 Data monitoring and processing module of host computer
In the intelligent parking system, the sensor network ultimately needs to communi-
cate with the Internet. There are two communication schemes at present: one is to install
Internet module or WIreless-FIdelity module directly on the hardware system, and the
sensor data can be directly submitted to the server. Another is the sensor network to
gather data to the host computer, and the host computer is responsible for communi-
cating with the Internet.
For the first scheme, each sensor node has the ability to communicate with the Inter-
net server, and the structure is clear and simple, easy to implement. But a large number
of sensor nodes communicating directly with the server will produce a large number of
invalid requests and increase the pressure of the server, and the power consumption of
the Internet block is large so that it is not suitable for the ow power hardware devices
in IoT. This scheme is only suitable for some IoT systems with simple scenes, single
functions and fewer nodes.
94 [Link]
Paper—A Routing Algorithm Based on Zigbee Technology
For the second scheme, the middle layer, that is, the data processing module of the
host computer, is added between the WSN and the Internet. The data processing module
of the host computer plays an important role in the system. On the one hand, the host
computer and ZigBee central node can read the status information of the vehicle, mon-
itor the running state of the current sensing network, and find and debug the problems
in the hardware system of the lower computer in time. On the other hand, the host com-
puter module is designed in accordance with the communication protocol of the IoT
(MQTT protocol). It receives the reverse control information from the server and for-
wards the control information to the ZigBee network through the serial port to control
the hardware response. To sum up, the function structure of the host computer data
processing module is shown in Figure 2.
Cloud server Submit sensor for your
status change
MQTT client HTTP client
Broadcast
Control Data cleaning
Instructions
Receive server message push to
control the lower computer
ZigBee network
Fig. 2. The function structure of the host computer data processing module
The host computer module monitors the running state of the sensor network, prepro-
cesses the sensor data, submits data to the server, avoids the direct access of the lower
machine to the server, reduces the pressure of the server, and receives message push
according to the communication protocol of the IoT.
3.4 Cloud server module
The IOT system is built on the traditional Internet system. The cloud server must be
able to meet high concurrency and high real-time performance because of the require-
ment of massive data request and real-time control in the IoT. Traditional server devel-
opment uses reverse proxy, multithreading or server cluster to improve the service per-
formance, but the corresponding technology is also complex and is not suitable for the
development of intelligent parking system prototype.
Based on the [Link] platform and MongoDB database, the cloud server programs
are developed, and hyper text transfer protocol (HTTP) services and message queuing
telemetry transport (MQTT) services are run on the [Link] platform to meet the re-
quirements of different scenarios. The [Link] platform uses JavaScript as a program-
ming language, and the MongoDB database stores data in the format of binary
iJOE ‒ Vol. 14, No. 11, 2018 95
Paper—A Routing Algorithm Based on Zigbee Technology
serialized document format. It has a good compatibility with the JavaScript language,
and the high concurrent query performance is excellent.
In this system, the cloud server needs two-way communication with the host com-
puter and the client. In the process of communication between the cloud server and the
host computer, the host computer submits data to the server through the HTTP protocol,
and the server pushes the control information to the host computer through the MQTT
protocol. In the process of communication between the cloud server and the client, the
server responds to the user's request to view the parking space and path planning
through the HTTP protocol, and responds to the user's demand for the reservation of
the parking lot space through the WebSocket (the MQTT protocol's alternative scheme
to the Web). The cloud server module is the data storage and distribution center of the
intelligent parking system. Its basic structure is shown in Figure 3.
Based on HTTP, Websocket
and client communication
MQTT proxy MongoDB
HTTP server
server database
[Link] platform
Based on HTTP, MQTT and PC
communication
Fig. 3. The basic structure of the cloud server module
3.5 User client module
The intelligent parking system will eventually show user client in front of users. In
practical applications, in order to facilitate the user's use of intelligent parking system,
the client needs to be provided on the mobile device. The Web application based on the
browser is designed in consideration of the difficulty of debugging, the difficulty of
development and the time cost.
The client provides the basic functions of the intelligent parking system for the user,
including the functions of the user registration and login, the statistics of total number
of parking spaces, the status of parking space, the book of parking space, and the plan-
ning path. The registration and login function is used to save user information, accept
user feedback, and restrict users to repeat multiple scheduled parking spaces. After en-
tering the system, users can use parking booking, parking path planning, parking guid-
ance, parking evaluation and other functions. Among them, path planning refers to gen-
erate the path from the location of the user to the location of the target parking lot, and
the parking guidance means the path from the entrance of a large parking lot to the
designated parking space.
96 [Link]
Paper—A Routing Algorithm Based on Zigbee Technology
4 Results
4.1 Parking guidance based on A routing algorithm
Extended valuation function: in the parking guidance system, according to the actual
situation, the valuation function used in the A* algorithm is extended. In the general
routing problem, the Manhattan distance is used as the valuation function, that is, the
Manhattan distance between two points (x1, y1) and (x2, y2) in the plane coordinate
system is |x1-x2|+|y1-y2|. This method is suitable for planning the path of only horizontal
or vertical two ways of walking. In the parking guidance, the car can walk along the
slant, that is, in the grid, it can walk along diagonal lines. In this way, the efficiency of
the algorithm can be improved. Therefore, the Manhattan distance is extended and its
calculation formula is shown below:
Dx = x1 - x2 . (1)
Dy = y1 - y2 . (2)
h(n ) = min (Dx, Dy ) * 2 + Dx, Dy . (3)
The extended Manhattan distance represents walking along the shortest diagonal line
first and then going straight to the target. It is expressed in a graphic manner, as shown
in Figure 4.
Fig. 4. Extended Manhattan distance calculation method
Execution process of A* routing algorithm: the most important thing in the imple-
mentation of A* algorithm is to maintain two lists, the open list and the close list. The
iJOE ‒ Vol. 14, No. 11, 2018 97
Paper—A Routing Algorithm Based on Zigbee Technology
open list stores the nodes to be processed, and the close list stores the nodes that are no
longer processed. The specific algorithm flow is shown in Figures 5 and 6.
Start
Set up open list and
close list
Add starting point
to open list
Open list is Y
empty
N
Find the bottom of the heuristic
value f from the open list
The grid with the smallest f value is
called currentNode
Transfer currentNode from open list
to close list
Looping around the grid around the
currentNode (subflow b)
N The target node was added to
the shutdown list
Go back from the target grid back to
the starting grid along the parent
node and draw the path
End
Fig. 5. The process of A* routing algorithm program
98 [Link]
Paper—A Routing Algorithm Based on Zigbee Technology
Start
Identifies the currently processed
adjacent cell as node[i]
Is Node[i] an obstacle or Y
already in the shutdown list?
Y Is Node[i] already in the N
open list?
The path calculates the new g value
Add node[i] to the open list
of node[i] via currentNode
Is the new g value of node[i] N
smaller than the old g value?
Record the g of node[i]
Y
Update the g of node[i]
Calculate the h and f values of
Calculate the h and f values of node[i]
node[i]
Set node[i]'s parent to currentNode
N Whether all adjacent nodes
have been processed
End
Fig. 6. The sub-process of A* routing algorithm for processing grids
4.2 Parking lot detection and control function test
The parking lot detection module is the data source of the system. Through a separate
test of the module, the system data can be optimized from the root to ensure the stability
of the hardware system.
Analysis of test results:
iJOE ‒ Vol. 14, No. 11, 2018 99
Paper—A Routing Algorithm Based on Zigbee Technology
First, the data that is read from the serial monitor is the data in a specific format. The
format of the data that the data acquisition module of the lower computer sends to the
host computer is "SensorId & cm&locx & locy", in which the SensorId value is the
node identifier defined in the current Arduino, that is, the number of parking lot. cm
represents the distance detected by the ultrasonic sensor and its unit is centimeter, and
locx and locy represent the location information of the current node, respectively.
Second, when the sensor is started, the data detected is not stable, but as time goes
on, the data gradually stabilizes and the error gradually decreases.
Third, when obstacle is used in the front of the ultrasonic transmitter, the value read
by the serial port becomes smaller immediately, indicating that the module can detect
the change of the parking lot. In the intelligent parking system, the ultrasonic sensor is
used to detect the change of the parking lot rather than the precise distance value. It is
required that the ultrasonic sensor can reflect the change correctly when there is obsta-
cle.
Fourth, when the data acquisition module is tested separately, the data is read directly
by the host computer through the universal serial bus to facilitate the debugging, and
the data will be transmitted to the host computer through the ZigBee network when the
system is run as a whole.
Fifth, when sending a control information through the serial monitor, the buzzer re-
sponds immediately, indicating that if the upper application sends the control infor-
mation in the convention format, the underlying hardware module can make a response.
In the experimental environment, the buzzer is used as a response to control infor-
mation, indicating that the parking lot is marked soft.
The test results show that the parking lot detection and control module can complete
the parking status detection and control the hardware response function.
4.3 Data forward flow test
The data forward flow refers to the process from the hardware system to the user
client interface after a series of system processing of the data collected by the ultrasonic
sensor. What finally displayed in front of users is the parking lot status information.
This part needs to test the four modules of the system after docking.
Testing procedure: in the process of this part of the test, it is necessary to first as-
semble and start the lower machine parking lot detection module and the server side
program, then start the host computer module which is used as the middle layer. When
necessary, the host computer program should be initialized first, and the page will be
opened to test the related functions manually. The flow chart of test process is shown
in Figure 7.
100 [Link]
Paper—A Routing Algorithm Based on Zigbee Technology
Start testing
Start parking detection The host computer opens the
module serial port data monitor and
submits the data
Start the cloud server
Open Web page test page
function
The upper computer Y
has id
End
The host computer gets
the id from the server
Fig. 7. The flow chart of data forward flow test process
Analysis of test results:
First, the parking lot detection module can effectively monitor the status of the ve-
hicle by ZigBee WSN, and the data are basically stable and correctly displayed in the
host computer interface.
Second, the server side runs HTTP services, MQTT services and WebSocket ser-
vices simultaneously. They are monitored in ports 3000, 1883, and 8081, and the ser-
vices run normally.
Third, the identification generation policy is running normally, the initialization data
can be stored in the database, and the unique identifier generated by the database will
be returned to the host computer.
Fourth, when the distance value measured by the ultrasonic sensor is less than the
set threshold, the status of the parking lot becomes occupied, and the change of the
parking lot state can also be seen in real time, even if the message is uploaded to the
server and the message is pushed to the user client.
Fifth, it can effectively locate the user's current position, plan the path from the user's
current position to the specific parking lot, and complete the parking path planning
function.
5 Conclusion
The demand of the user's parking is analyzed first, the basic function of the intelli-
gent parking system is determined according to the user's demand, and the overall
scheme of the system is put forward. The key technology used in it is compared, the
technical route of solving the system problem is made, and the overall structure of the
system is designed. Under the guidance of the overall structure, each function module
iJOE ‒ Vol. 14, No. 11, 2018 101
Paper—A Routing Algorithm Based on Zigbee Technology
is realized, including the parking lot detection module, the host computer data pro-
cessing module, the cloud server module and the Web client module. Finally, the sys-
tem is analyzed and tested from three aspects, including the data acquisition module of
the lower computer (parking lot detection and control module), and the forward flow
test of the system data, which verifies the feasibility of the basic function of the whole
system prototype. The test and analysis results show that the intelligent parking system
based on ZigBee can provide the functions of online parking field search, parking status
view, path planning and online parking space reservation for users with parking de-
mand, which can help to solve the problem of parking difficulty.
6 References
[1] Choe, H., Gorfman, S., Heidbrink, S. (2017). Multichannel FPGA-Based Data-Acquisition-
System for Time-Resolved Synchrotron Radiation Experiments. IEEE Transactions on Nu-
clear Science, 64(6): 1320-1326. [Link]
[2] Vlahogianni, E.I., Kepaptsoglou, K., Tsetsos, V. (2016). A real-time parking predic-tion
system for smart cities. Journal of Intelligent Transportation Systems, 20(2): 192-204.
[Link]
[3] Liu, X., Wang, X., Wright, G. (2017). A State-of-the-Art Review on the Integration of Build-
ing Information Modeling (BIM) and Geographic Information System (GIS). ISPRS Inter-
national Journal of Geo-Information, 6(2): 53. [Link]
[4] Song, Y., Lin, J., Tang, M. (2017). An Internet of Energy Things Based on Wireless
LPWAN. Engineering, 3(4): 460-466. [Link]
[5] Khan, I., Belqasmi, F., Glitho, R. (2016). Wireless sensor network virtualization: A survey.
IEEE Communications Surveys & Tutorials, 18(1): 553-576. [Link]
COMST.2015.2412971
[6] Khan, A.A., Rehmani, M.H., Reisslein, M. (2016). Cognitive radio for smart grids: Survey
of architectures, spectrum sensing mechanisms, and networking protocols. IEEE Communi-
cations Surveys & Tutorials, 18(1): 860-898. [Link]
2481722
[7] Moridi, M.A., Kawamura, Y., Sharifzadeh, M. (2018). Performance analysis of ZigBee net-
work topologies for underground space monitoring and communication systems. Tunnelling
and Underground Space Technology, 71: 201-209. [Link]
.08.018
[8] Han, G., Jiang, J., Zhang, C. (2016). A survey on mobile anchor node assisted localiza-tion
in wireless sensor networks. IEEE Communications Surveys & Tutorials, 18(3): 2220-2243.
[Link]
7 Author
Xieji Gang works as Nanjing institute of industry technology, Jiangsu, China.
Article submitted 09 September 2018. Resubmitted 13 October 2018. Final acceptance 17 October 2018.
Final version published as submitted by the authors.
102 [Link]
