> ^
tY
TkimoqsuLNLN_ a!!c"""""""""&&'q((q))q**q++q,,q--z.@ R*bjbjFF,,777M 8
T*MNlF X Y Y Y r
rf
L$lR^77
m
,r
7Y Y
"Y 7Y
~*t
7%
Y `F p@D Q
,
L
0
H
xX%
8D~7%
F
t
.
t
F
F
F
77MM_ew
"MM SHAPE \* MERGEFORMAT
Abstract
This report is written to summarize all the work of our final year project entitled Location-Based Multimedia Mobile Service in the first semester. During the first semester, we mainly focus on the problem of localization. Therefore, in the second semester, base on our knowledge and developed tools in localization, we are able to further develop a location-based multimedia service system.
In the last semester, we have chosen the 1st floor of the Ho Sin-Hang Engineering Building, the Chinese University of Hong Kong to study the problem of localization. Our goal is to locate a person when he/she is walking around on the floor. To achieve the goal, we have encountered a lot of problems. For example, how to collect the signals from the Wireless LAN access points, how to process the data, how to choose and apply algorithms in order to use the collected signals and so on. Every problem mentioned will affect the accuracy in localization. Therefore, in this report, we are going to introduce how we can solve these problems.
In the second semester, we focus on the improvement of the localization system and the implementation of a location-based multimedia service system. We have introduced continuous space estimation in localization, point mapping and Dijsktras algorithm so as to improve the accuracy and functioning of our system. We have also implemented Multimedia Guidance System (MGS). This tool is mainly to assist developers to deploy Localization-Based Multimedia Service System.
We first give an introduction about the current issue of localization in recent years. Chapter 2 is Wireless LAN fundamentals will help you to understand some terms and standard in WLAN as well as our project. In the next section, we introduce different approaches and algorithms in localization, so that you have a brief idea on how to achieve localization. After that, we will give a detail description on how we apply the Area-Based Probability algorithm and solve the problems we face. We will also list out the result of the experiments that we have done on the accuracy of our system.
In chapter 6, we describe the advantages and the way of using continuous space estimation. We also include an experiment we have done to evaluate the performance of continuous space estimation. The next chapter, we will introduce point mapping and Dijsktras algorithm that used in our guide service application. Then, we will talk about the details in Multimedia Guidance System (MGS). This tool includes 3 parts. They are Wi-Fi Signal Scanner (WSS), Multimedia Guidance Processor (MGP) and Localization-Based Multimedia Service System (LBMSS).
At the end, we will give a brief summary and a listing of the problem that we have faced together with our solution. Then we will describe our contribution to the project. The last section is our project progress in the semester.
TOC \o "1-3" \h \z \u
HYPERLINK \l "_Toc101671001" 1. Introduction PAGEREF _Toc101671001 \h 7
HYPERLINK \l "_Toc101671002" 2. Introduction to Wireless Network PAGEREF _Toc101671002 \h 9
HYPERLINK \l "_Toc101671003" 2.1 Access Point (AP) PAGEREF _Toc101671003 \h 9
HYPERLINK \l "_Toc101671004" 2.2 Wireless Terminology PAGEREF _Toc101671004 \h 9
HYPERLINK \l "_Toc101671005" 2.3 Wireless Standard PAGEREF _Toc101671005 \h 10
HYPERLINK \l "_Toc101671006" 2.4 Open System Interconnection (OSI) 7 Layer Model PAGEREF _Toc101671006 \h 12
HYPERLINK \l "_Toc101671007" 3. Algorithms in Localization PAGEREF _Toc101671007 \h 15
HYPERLINK \l "_Toc101671008" 3.1 Terms and Definitions PAGEREF _Toc101671008 \h 15
HYPERLINK \l "_Toc101671009" 3.2 Generating a Training Set PAGEREF _Toc101671009 \h 17
HYPERLINK \l "_Toc101671010" 3.3 Distance Mapping Algorithm PAGEREF _Toc101671010 \h 18
HYPERLINK \l "_Toc101671011" 3.4 Point-Based Approach VS Area-Based Approach PAGEREF _Toc101671011 \h 19
HYPERLINK \l "_Toc101671012" 3.5 Simple Point Matching Algorithm PAGEREF _Toc101671012 \h 20
HYPERLINK \l "_Toc101671013" 3.6 Area Based Probability PAGEREF _Toc101671013 \h 22
HYPERLINK \l "_Toc101671014" 4. Experiments and Implementation of Localization Algorithm PAGEREF _Toc101671014 \h 25
HYPERLINK \l "_Toc101671015" 4.1 Our Choice of Algorithm PAGEREF _Toc101671015 \h 25
HYPERLINK \l "_Toc101671016" 4.2 Applying the Area-Based Approach PAGEREF _Toc101671016 \h 27
HYPERLINK \l "_Toc101671017" 4.3 Generating Training Set PAGEREF _Toc101671017 \h 28
HYPERLINK \l "_Toc101671018" 4.4 Method in Getting the Testing Set PAGEREF _Toc101671018 \h 30
HYPERLINK \l "_Toc101671019" 4.5 Finding Probabilities at Locations PAGEREF _Toc101671019 \h 31
HYPERLINK \l "_Toc101671020" 4.5.1 Applying Bayles Rule PAGEREF _Toc101671020 \h 31
HYPERLINK \l "_Toc101671021" 4.5.2 Finding the Probability P(slj | Ai) PAGEREF _Toc101671021 \h 32
HYPERLINK \l "_Toc101671022" 4.5.3 Finding Integral of the Gaussian distribution function PAGEREF _Toc101671022 \h 34
HYPERLINK \l "_Toc101671023" 4.5.4 Finding Probability P(St | Ai) PAGEREF _Toc101671023 \h 35
HYPERLINK \l "_Toc101671024" 4.6 Experiment Result PAGEREF _Toc101671024 \h 37
HYPERLINK \l "_Toc101671025" 5. Analysis of Experiment Results PAGEREF _Toc101671025 \h 50
HYPERLINK \l "_Toc101671026" 5.1 Performance of Area-Based Probability Algorithm PAGEREF _Toc101671026 \h 50
HYPERLINK \l "_Toc101671027" 5.2 Accuracy of our localization system PAGEREF _Toc101671027 \h 51
HYPERLINK \l "_Toc101671028" 5.3 The effect of number of samples on accuracy PAGEREF _Toc101671028 \h 52
HYPERLINK \l "_Toc101671029" 5.4 Other factors affecting the accuracy PAGEREF _Toc101671029 \h 53
HYPERLINK \l "_Toc101671030" 5.4.1 Hardware failure PAGEREF _Toc101671030 \h 53
HYPERLINK \l "_Toc101671031" 5.4.2 Change in environment PAGEREF _Toc101671031 \h 54
HYPERLINK \l "_Toc101671032" 5.4.3 Orientation in collecting signal PAGEREF _Toc101671032 \h 54
HYPERLINK \l "_Toc101671033" 6. Center-of-Mass technique in Continuous Space Estimation PAGEREF _Toc101671033 \h 56
HYPERLINK \l "_Toc101671034" 6.1 Limitation of Discrete Space Estimation PAGEREF _Toc101671034 \h 56
HYPERLINK \l "_Toc101671035" 6.2 Center-of-Mass in Continuous Space Estimation PAGEREF _Toc101671035 \h 56
HYPERLINK \l "_Toc101671036" 6.3 Applying Center of Mass technique in the Guide Service PAGEREF _Toc101671036 \h 57
HYPERLINK \l "_Toc101671037" 7. Evaluation of the Accuracy of Centre of Mass in Continuous Space Estimation PAGEREF _Toc101671037 \h 58
HYPERLINK \l "_Toc101671038" 7.1 Methodology PAGEREF _Toc101671038 \h 58
HYPERLINK \l "_Toc101671039" 7.2 Experiment Result PAGEREF _Toc101671039 \h 59
HYPERLINK \l "_Toc101671040" 7.3 Analysis of Experiment Result PAGEREF _Toc101671040 \h 77
HYPERLINK \l "_Toc101671041" 8. Point Mapping technique in the Guide Service PAGEREF _Toc101671041 \h 79
HYPERLINK \l "_Toc101671042" 8.1 The Aim of Point Mapping Technique PAGEREF _Toc101671042 \h 79
HYPERLINK \l "_Toc101671043" 8.2 Applying Point Mapping Technique PAGEREF _Toc101671043 \h 79
HYPERLINK \l "_Toc101671044" 8.3 Evaluation of Point Mapping Technique in Continuous Space Estimation PAGEREF _Toc101671044 \h 82
HYPERLINK \l "_Toc101671045" 8.3.1 Methodology PAGEREF _Toc101671045 \h 82
HYPERLINK \l "_Toc101671046" 8.3.2 Experiment Result PAGEREF _Toc101671046 \h 83
HYPERLINK \l "_Toc101671047" 8.3.3 Summary of the Experiment Statistics PAGEREF _Toc101671047 \h 92
HYPERLINK \l "_Toc101671048" 8.3.4 Analysis of Experiment Result PAGEREF _Toc101671048 \h 92
HYPERLINK \l "_Toc101671049" 9. Shortest Path Algorithm in the Guide Service PAGEREF _Toc101671049 \h 93
HYPERLINK \l "_Toc101671050" 9.1 Introduction to Shortest Path Problem PAGEREF _Toc101671050 \h 93
HYPERLINK \l "_Toc101671051" 9.2 Applying Dijkstras algorithm in the Guide Service PAGEREF _Toc101671051 \h 93
HYPERLINK \l "_Toc101671052" 9.3 Pseudo code of Dijkstra's Algorithm PAGEREF _Toc101671052 \h 97
HYPERLINK \l "_Toc101671053" 9.4 Example of Dijkstras Algorithm PAGEREF _Toc101671053 \h 97
HYPERLINK \l "_Toc101671054" 10. Multimedia Guidance System PAGEREF _Toc101671054 \h 107
HYPERLINK \l "_Toc101671055" 10.1 Introduction PAGEREF _Toc101671055 \h 107
HYPERLINK \l "_Toc101671056" 10.2 Deploying Procedure PAGEREF _Toc101671056 \h 108
HYPERLINK \l "_Toc101671057" 10.3 Features of Multimedia Guidance System (MGS): PAGEREF _Toc101671057 \h 109
HYPERLINK \l "_Toc101671058" 10.4 Wi-Fi Signal Scanner (WSS) PAGEREF _Toc101671058 \h 111
HYPERLINK \l "_Toc101671059" 10.4.1 Software Architecture PAGEREF _Toc101671059 \h 111
HYPERLINK \l "_Toc101671060" 10.4.2 Network Driver Interface Specification (NDIS) PAGEREF _Toc101671060 \h 112
HYPERLINK \l "_Toc101671061" 10.4.3 Feature of Wi-Fi Signal Scanner PAGEREF _Toc101671061 \h 114
HYPERLINK \l "_Toc101671062" 10.4.4 Collecting Data Procedure using Wi-Fi Signal Scanner PAGEREF _Toc101671062 \h 116
HYPERLINK \l "_Toc101671063" 10.4.5 Analysis the Data in Wi-Fi Signal Scanner PAGEREF _Toc101671063 \h 117
HYPERLINK \l "_Toc101671064" 10.5 Multimedia Guidance Processor (MGP) PAGEREF _Toc101671064 \h 119
HYPERLINK \l "_Toc101671065" 10.5.1 Overview of MGP PAGEREF _Toc101671065 \h 119
HYPERLINK \l "_Toc101671066" 10.5.2 Data Processing Procedure in MGP PAGEREF _Toc101671066 \h 121
HYPERLINK \l "_Toc101671067" 10.5.3 Feature of Multimedia Guidance Processor PAGEREF _Toc101671067 \h 129
HYPERLINK \l "_Toc101671068" 10.6 Location-Based Multimedia Service System (LBMSS) PAGEREF _Toc101671068 \h 131
HYPERLINK \l "_Toc101671069" 10.6.1 System architecture PAGEREF _Toc101671069 \h 131
HYPERLINK \l "_Toc101671070" 10.6.2 Paint Server PAGEREF _Toc101671070 \h 132
HYPERLINK \l "_Toc101671071" 10.6.3 Media Server PAGEREF _Toc101671071 \h 135
HYPERLINK \l "_Toc101671072" 10.6.4 Chat and Management Server PAGEREF _Toc101671072 \h 138
HYPERLINK \l "_Toc101671073" 10.6.5 Mobile client PAGEREF _Toc101671073 \h 141
HYPERLINK \l "_Toc101671074" 10.6.6 Preparation Procedure PAGEREF _Toc101671074 \h 149
HYPERLINK \l "_Toc101671075" 10.7 Summary of Multimedia Guidance System (MGS) PAGEREF _Toc101671075 \h 150
HYPERLINK \l "_Toc101671076" 11. Summary PAGEREF _Toc101671076 \h 153
HYPERLINK \l "_Toc101671077" 12. Problem and solution PAGEREF _Toc101671077 \h 155
HYPERLINK \l "_Toc101671078" 13. Contribution of work PAGEREF _Toc101671078 \h 161
HYPERLINK \l "_Toc101671079" 13.1 Introduction PAGEREF _Toc101671079 \h 161
HYPERLINK \l "_Toc101671080" 13.2 Preparation Work PAGEREF _Toc101671080 \h 161
HYPERLINK \l "_Toc101671081" 13.3 Detection of Access Point Signals and Retrieval of Signal Strengths PAGEREF _Toc101671081 \h 162
HYPERLINK \l "_Toc101671082" 13.4 Data Processing of Collected Signals PAGEREF _Toc101671082 \h 163
HYPERLINK \l "_Toc101671083" 13.5 Location Detection PAGEREF _Toc101671083 \h 163
HYPERLINK \l "_Toc101671084" 13.6 Multimedia Add-on Service PAGEREF _Toc101671084 \h 164
HYPERLINK \l "_Toc101671085" 13.6.1 Guide Service PAGEREF _Toc101671085 \h 164
HYPERLINK \l "_Toc101671086" 13.6.2 Other Service PAGEREF _Toc101671086 \h 165
HYPERLINK \l "_Toc101671087" 13.7 Conclusion PAGEREF _Toc101671087 \h 165
HYPERLINK \l "_Toc101671088" 14. Schedule of Project PAGEREF _Toc101671088 \h 166
HYPERLINK \l "_Toc101671089" 15. Acknowledgement PAGEREF _Toc101671089 \h 169
HYPERLINK \l "_Toc101671090" 16. References PAGEREF _Toc101671090 \h 170
HYPERLINK \l "_Toc101671091" 17. Appendix PAGEREF _Toc101671091 \h 174
1. Introduction
Localization is necessary for many higher level sensor network functions such as tracking, monitoring and geometric-based routing. There are many applications that provide services based on the location of the user, such as telephone follow me, which forwards phone calls to the users current location, everywhere printing, which chooses the nearest printer for mobile users, and intelligent tourist, which offers help information based on a tourists location.
Many positioning systems designed to determine or track a users location have been proposed in recent years. Those systems fall into three categories: global location systems, wide-area location systems based on cellular networks, and indoor location systems.
A typical global location system is the Global Positioning System (GPS), which receives signals from multiple satellites and employs a triangulation process to determine physical locations with an accuracy of approximately 10 m. However, GPS is inefficient for indoor use or in urban areas where high buildings shield the satellite signals.
Several cellular-network-based wide-area location systems have been proposed in recent years. The technological methods of location determination involve measuring the signal strength, the angle of signal arrival, and/or the time difference of signal arrival. However, the accuracy of wide-area location systems is highly limited by the cell size. Moreover, the effectiveness of systems for an indoor environment is also limited by the multiple reflections suffered by the radio frequency (RF) signal.
For an indoor environment, several systems based on various technologies such as infrared (IR), ultrasound, video surveillance, and radio signal are emerging. Among these systems, radio-signal-based approachesmore specifically, the wireless local-area network (WLAN) (IEEE 802.11b, also named Wi-Fi) radio-signal-based positioning systemhave drawn great attention in recent years.
A WLAN-based positioning system has distinct advantages over all other systems. First, it is an economical solution because the WLAN network usually exists already as part of the communications infrastructure. For a notebook computer, personal digital assistant (PDA), or other mobile devices equipped with WLAN capability, the positioning system can be implemented simply in softwaregenerally in middleware or at the application level. This software based location system significantly reduces cost with respect to dedicated architectures.
Second, the WLAN-based positioning system covers a large area compared with other types of indoor positioning systems. The WLAN-based positioning system may work in a large building or even across many buildings. Third, it is a stable system owing to its robust RF signal propagation. Video- or IR-based location systems are subject to restrictions, such as line-of-sight limitations or poor performance with fluorescent lighting or in direct sunlight.
In this innovative WLAN-based indoor positioning technology, the signal strength distribution of WLAN access points is collected to train a position-determination model. The training phase is followed by the working phase, during which the mobile device observes the WLAN signals and applies the position-determination model to calculate a position. To reduce the complexity of the training phase, the position-determination model is only trained from a limited amount of collected samples. To improve the accuracy of the location system, a localization algorithm is introduced in which the position determination relies on both collected signal strength and knowledge of space topology.
We have set up the WLAN-based positioning system on the first floor of the Ho Sin-Hang Engineering Building. The system is installed in Personal Digital Assistant (PDA) with Window CE as its platform. Based on the positioning technology, we further developed the Multimedia Guidance System (MGS). It not as simple as a multimedia application, but it is a tool to assist developers to deploy Localization-Based Multimedia Service System.
2. Introduction to Wireless Network
2.1 Access Point (AP)
It is a hardware device or a computer's software that acts as a communication link for user to access the wired Local Area Network (LAN). Each Access Point has a unique Network Interface Card (NIC). User can communicate the Access Point through this interface.
2.2 Wireless Terminology
Media Access Control address (MAC Address)
It is a unique hardware address that identifies each node in the network. Referencing to OSI 7 Layer Model, the Data Link Control (DLC) layer in the IEEE 802 network is divided into two sub layers: the Logical Link Control (LLC) layer and the Media Access Control (MAC) layer. And each different type of network medium requires a different MAC layer.
Those networks that do not confirm to IEEE 802 standards, the nodes in the network are called Data Link Control (DLC) address.
Service set identifier (SSID)
It is a 32 character. It adds to the header of packets that acts as a password when mobile device sends the packet through Wireless Local Area Network (WLAN). The SSID in one WLAN is different from another. All access points and mobile devices connecting to a specific WLAN must use the same SSID. They can be permitted to join the WLAN provided that they can provide the unique SSID. However, SSID can be sniffed in WLAN which easily get from a packet. It does not supply any security to WLAN.
Receive Signal Strength Indicator (RSSI)
It is the signal strength received by the mobile device in the WLAN. Its unit is in dBm. The smaller values of RSSI, the greater strength received by the mobile device. RSSI is a negative integer number.
Wireless Fidelity (Wi-Fi)
The Terms Wireless Fidelity is published by Wi-Fi Alliance. Formerly, the term Wi-Fi was only referring to IEEE 802.11b. Now, Wi-Fi generally means the all type of wireless network, including IEEE 802.11a, IEEE 802.11b, etc. Any networking products are tested by Wi-Fi Alliance. It is certificated as Wi-Fi Certified. This guarantee Wi-Fi Certified product can communicate with other Wi-Fi Certified product without problem.
Wired Equivalent Privacy (WEP)
It is a security protocol for wireless Local Area Network (WLAN). It aims to be protected from unauthorized access. It protects the WLAN by encrypting the data over the radio channel. However, it found that WEP can be cracked by advanced technique. WEP is used at the two lowest layers of the Open System Interconnection ( HYPERLINK "http://www.webopedia.com/TERM/W/%20http:/webopedia.internet.com/quick_ref/OSI_Layers.asp" OSI) model - the data link and physical layers; it therefore does not offer end-to-end security.
Wi-Fi Protected Access (WPA)
It is designed to improve upon the security features of WEP. It can work with existing Wi-Fi products that have been enabled with WEP. It improves data encryption through temporal key integrity protocol (TKIP). And it adds HYPERLINK "http://www.webopedia.com/TERM/W/authentication.html" authentication through the HYPERLINK "http://www.webopedia.com/TERM/W/EAP.html" extensible authentication protocol (EAP). EAP is a more secure encryption system ensuring only authorized users can access the WLAN.
2.3 Wireless Standard
IEEE 802.11
It is a family of wireless Local Area Network (WLAN) specifications developed by Institute of Electrical and Electronics Engineers (IEEE).
Currently, there are four specifications in IEEE 802.11 family:
IEEE 802.11
IEEE 802.11a
IEEE 802.11b
IEEE 802.11g
802.11e and 802.11i will be approved in 2004
IEEE 802.11
It operates on the 2.4 GHz band using either direct sequence spread spectrum (DSSS) or frequency hopping spread spectrum (FHSS). It provides up to 2 Mbps transmission rate.
IEEE 802.11a
It operates on 5 GHz band using orthogonal frequency division multiplexing encoding scheme (OFDM). It provides up to 54 Mbps transmission rate. It is not interoperable with IEEE 802.11b. Only eight channels are available.
IEEE 802.11b
It is often called Wi-Fi. It operates on 2.4 GHz using direct-sequence spread spectrum (DSSS) with complementary code keying (CCK). This allows high access to data at up to 300 feet from base station. It provides up to 11 Mbps transmission rate. Fourteen channels are available for this standard. Only eleven channels can be used in the United States due to Federal Communications Commission (FCC) regulations. Comparing to IEEE 802.11a, it requires fewer access points to cover large areas.
IEEE 802.11g
It operates on 2.4 GHz band. It provides up to 54 Mbps transmission rate. It uses orthogonal frequency division multiplexing encoding scheme (OFDM) when transmission rate is above 20 Mbps. Otherwise, it uses direct-sequence spread spectrum (DSSS) with complementary code keying (CCK). It improves security enhancements over 802.11. It is compatible with IEEE 802.11b. Fourteen channels are available in the 2.4 GHz band.
IEEE 802.11e
It is the first standard that targets on home and business environment. It has Quality-of-Service (QoS) in this standard. It adds multimedia support to the existing IEEE 802.11b and IEEE 802.11a wireless standards such that it has a full compatibility with previous standard. It can implement in following kinds of application, e.g. Video on demand, audio on demand, voice over IP (VoIP) and high-speed Internet access, etc.
IEEE 802.11i
It adds theAdvanced Encryption Standard (AES) security protocol. This protocol is much stringer than the Wi-Fi Protected Access security standard (WFA) which implemented in the previous standard.
2.4 Open System Interconnection (OSI) 7 Layer Model
The model defines a networking framework in seven layers. It is divided into 7 Layer. The protocol is implemented according to each layer requirement in the model. Control in each layer is passed from one layer to next layer , starting at the top layer(application layer) to the bottom layer(physical layer) over the channel to the next station and back up the layer from the bottom layer to top layer.
The following is the OSI 7 Layer Model:
ApplicationPresentationSessionTransportNetworkData LinkPhysical Figure 2.1
Application Layer (Layer 7)
Layer 7 is the Application Layer. This layer defines the end-user and end-application protocols, such as telnet, http, and ftp. Everything is application-specific must be defined or implemented in this layer.
Presentation Layer (Layer 6)
Layer 6 is the Presentation Layer. This layer defines the data representation. It formats the data into specific format before transmit to the outside network. Protocol conversions, encryption/ decryption and graphics expansion are all implemented in this layer.
Session Layer (Layer 5)
Layer 5 is the Session Layer. It establishes, manages and terminates connections between applications in the station. This layer handling sets up, coordinates, and terminates conversations, exchanges, and dialogues between the applications at station.
Transport (Layer 4)
Layer4 is the Transport Layer. This layer handles the transferring data between end systems. It provides the end-to-end error recovery and flow control. It ensures the data can transfer correctly. Transmission ControlProtocol (TCP) and User Datagram Protocol (UDP) is the example that implement in this layer.
Network (Layer 3)
Layer3 is the Network Layer. This layer provides communication between the end system by switching and routing technologies. It also handles addressing, internetworking, error handling, congestion control and packet sequencing. Internet Protocol (IP) is the protocol implementing in this layer.
Data Link (Layer 2)
Layer2 is the Data Link Layer. It is divided into two sub layers: The Media Access Control (MAC) layer and the Logical Link Control (LLC) layer. The MAC layer controls how computer sending and receiving the data on the network. The LLC layer controls frame synchronization, flow control and error checking.
Physical (Layer 1)
Layer1 is the Physical Layer. It defines the physical and electrical signal of the network. The Network Interface Card (NIC) in the computer and the interfaces in the network equipments all run at this level.
3. Algorithms in Localization
3.1 Terms and Definitions
In order to understand the algorithm used in localization in a more systematic and formal way, we introduce some terms and definitions which are commonly used to describe Localization algorithm in wireless LAN.
A wireless LAN access point is represented by AP. Suppose there are n Access Points on the floor, they are represented by AP1, AP2, , APn. Also, we assume that there are total m areas to be located, that is they can be represented by A1, A2, , Ak. The offline measured signal strengths and locations an algorithm used is called the training set T0. A training set (T0) consists of a set of fingerprints (Si) at m different areas Ai. More mathematically, T0 can be represented by this equation, T0 = {( Ai, Si )}, i = 1 m.
So, what is a fingerprint S? Si is the set of expected average signal strengths measured from APs at a particular area Ai. As there are totally n APs, so a fingerprint Si should have n elements and each of them is from one AP. More formally, Si = (si1, , sin), where sij is the expected average signal strength from APj.
SHAPE \* MERGEFORMAT
Figure 3.1 summarizes the structure of a training set
Received signal strength (RRS) refers to the signal strengths received from APs by the mobile device when a user uses it for localization. RRS is similar to a fingerprint. It contains the set of signal strengths measured from APs at the current position. The number of elements in RRS depends on how many access points the mobile device can detect at the current position.
SHAPE \* MERGEFORMAT
Figure 3.2 summarizes the structure of a RRS
3.2 Generating a Training Set
As mentioned above, a Training Set is the offline measured signal strengths and locations an algorithm used in localization. A training set is essential for localization because it records the characteristics of different areas to be located. A training set is later used by an algorithm to distinguish different locations and find out the best fit location when a testing set is applied. A testing set is measured at real time when a person uses a mobile device to locate himself/herself. Therefore, it is important to prepare a training set for localization. The following will show a common way to generate a training set step by step.
In order to get the expected average signal strength from a particular APj at Ai, we need to read a series of signal strengths (sijk ) for this particular APj with a constant time between samples. After that, we calculate sij by averaging the series, {sij1, sij2, sijoij }, where oij is the number of samples from APj at Ai.
Then, we can generate Si by using the above method and measure n series of signal strengths (sijk ) for all the n APs. Finally, we use the same method to generate the fingerprints S at all m areas to be located and hence we will generate the training set.
3.3 Distance Mapping Algorithm
This algorithm is a simple algorithm which does not require a training set. So, it can be implemented more quickly. We first find out the locations of all the wireless LAN access points. During the localization, we create a testing set by measuring the signal strengths received locally from different access points. Then, we use the assumption that the distance between the current location and a particular access point is in direct proportion with the signal strengths measured from the access point.
Therefore, the possible locations that we can predict from the signal strengths from one particular AP are in a circular shape illustrated. In order to find the current location, we need to minimize the set of possible locations. It can be done easily by overlapping each of the circular set of possible locations predicted by different APs. Figure 3.3 shows how we can apply this algorithm and find out the current location. With stronger signal strengths received from an AP, the distance from it is smaller and so the circle illustrated in the figure is smaller. On the other hand, if the signal strengths received are weaker, the distance from it is longer and hence a larger circle.
SHAPE \* MERGEFORMAT
3.4 Point-Based Approach VS Area-Based Approach
There are mainly two approaches used in localization, namely, the point-based approach and the area-based approach. Previous WLAN localization work often uses the traditional point-based approach to localization. In these approaches, the localization goal is to return a single point of possible location for the object to be located.
The above Distance Mapping algorithm is a simple algorithm using the point-based approach. However, in our case for a WLAN-enabled mobile device, we have used a novel area-based approach for WLAN localization systems based on the advantages of using this approach. The goal in an area-based localization system is to return a possible location of the mobile object as an area rather than a single location. So, in our case, we will return area of rooms, the areas of corridor corners or the area of corridor in front of certain rooms as the output result.
The advantages of area-based approaches arise from the fundamental uncertainty resulting from probabilistic approaches used by WLAN localization systems. Area-based systems are better able to utilize and describe this uncertainty in a meaningful manner as compared to point-based approaches.
One advantage is that area-based approaches can direct the user in his search for an object in a more systematic manner as compared to point-based approaches. For example, when looking for lost keys using an area-based approach, the user can begin his search for the keys in the most likely area maybe at room 101. Then he continually expands his search to the next most likely area maybe to room 102. The user thus searches in a systematic manner in relation to the likelihood of the objects presence in the area.
A second advantage of area-based localization is that it presents the user an understanding of the system in a more natural and intuitive manner than a point-based approach. If our system returns Rm101 as the result, the user will have a better confidence for its location rather than returning a point with x and y coordinates.
The critical property that area-based systems exhibit in dealing with the uncertainty is their ability to trade accuracy for precision. Intuitively, localization accuracy is the error between the estimated position and the objects true position. For area-based systems, we define accuracy as the distance the object is from the returned area. Precision describes the size of the area. A point is infinitely precise, but may not be very accurate. On the other hand, the area containing the entire scope of the localization system (e.g. the whole building) would have a high accuracy but poor precision. In order to achieve our goal to apply localization on 1st floor of the engineering building, we are not required to have a result as precise as a point; however, we apply the area-based approach to increase the accuracy for the WLAN-based system to localize objects.
3.5 Simple Point Matching Algorithm
The strategy behind Simple Point Matching (SPM) is to find a set of areas(Ai) that fall within a threshold of the RSS for each AP independently, and then return the area(s) that forms the intersection of each APs set. Figure 3.4 describes SPM in pseudo code.
Figure 3.4
The Grid, = (1, . . . , n), FT , and Area, correspond to the a vector of the expected signals standard deviation received from each AP, a set of all the tiles on the floor, and the returned area, respectively.
More formally, SPM first finds n sets of areas, one for each APj , j = 1 . . . n, that match all fingerprints Sl = (sl1, . . . , sln). The matching areas for each APj are found by adding an expected noise level, q to slj, and then by returning all the floor areas that fall within the expected threshold, slj q (we may substituted a value of -92 dBm for missing signals). SPM then returns the area formed by intersecting all matched areas from the different AP area sets.
For increasing the precision of the algorithm, i.e., to find the fewest high probability areas, it starts from a very low q. However, it then runs into the risk of returning no areas when one of the area sets returned from a particular AP is empty. Thus, on an empty intersection, the algorithm additively increases q, i.e., it first tries q, 2q, 3q, , until a non-zero set of tiles results. Therefore, even in the worst case, a non-empty intersection will result when q is large enough.
An important issue is the how to pick the q for each APj. An intuitive way is to pick the expected standard deviation of the signals received from APj. For simplicity, you may pick 10 as the standard deviation for all APs as it is commonly used by localization. However, the standard deviation can vary from an access point to another, depending on the strength of the signal. Therefore, different standard deviation can be used as the threshold q for each AP to increase the accuracy in localization.
3.6 Area Based Probability
The strategy used by the Area-Based Probability (ABP) algorithm is to return a set of areas bounded by a probability that the object is within the returned set. We call the probability, , the confidence, and it is an adjustable parameter.
To find a result area set, ABP computes the likelihood of received signal strength (RSS) that matches the fingerprints of each area in the training set (T0). Then it normalizes these likelihoods given the prior conditions: (1) the object must be on floor, and (2) all areas are a-priori equally likely to be visited. ABP then returns the top probability areas whose sum matches the desired confidence.
The confidence controls the accuracy-precision tradeoff. ABP thus stands on a more formal mathematical foundation than SPM. Figure 3.5 summarizes the ABP algorithm.
Figure 3.5
In ABP, signals received from different access points are assumed to be independent. For each APj , j = 1 . . . n, the sequence of received signal strengths sijk, k = 1 . . . oij , at each (xi, yi) in the original training set, T0, is modeled as a Gaussian distribution. Although this assumption is not generally true, it significantly simplifies the computations with little performance degradation.
To apply the algorithm, we first generate a training set by the procedure mentioned in Section 3.2. Then, we compute the mean parameter of the distribution, sij for each fingerprint in the original training set T0. For each APj , we assume that the standard deviation of the distribution at all the areas on the floor is constant, and equals to j.
The algorithm use Bayes rule to compute the probability of being at each location, Li, on the floor given the testing set Sl, i.e., the received signal strength of the object to be located. The Bayes rule is given below:
P(Sl | Li) is the probability of having the testing set Sl when having known the current location is at Li. P(Sl) is the probability of receiving this set of signal strengths Sl and P(Li) is the probability at the location Li.
However, P(Sl) is a constant c1. Moreover, given we do not have prior knowledge about the exact objects location. We assume that the object to be localized is equally likely to be at any location on the floor. So, P(Li) = P(Lj), for all i and j and P(Li) = c2 for all i, where c2 is another constant. Therefore, after we let c= c2/ c1, equation (1) is rewritten as equation (2) as follow:
By using equation (2), we can derive the following:
Max{P(Ai |St) } = Max{c*P(St | Ai) } = Max{P(St | Ai) } (3)
Without having to know the value c, we can just return the location (area Ai) with maximum of P(Sl | Ai). In order to compute P(Sl | Ai) for all areas, we use the whole set Sl = (sl1, . . . , sln) for computing the probability, i.e., signal strengths from all the access points. We also substitute a value of -92 dBm for missing signals, when the current location is not covered by the access point.
Let P(slj | Ai) be the probability of having a signal strength of slj from APj given the location is at Ai. P(slj | Ai) can be found by using our Gaussian distribution assumption. The follow is the equation of Gaussian distribution:
(4)
So, we compute P(Sl | Ai) by using the formula of independent event in probability:
P(Sl | Ai) = P(sl1 | Ai) X P(sl2 | Ai) X X P(sln | Ai) (5)
Given that the object must be at exactly at one area, i.e., P(Ai | Sl) =1 for all I,
ABP computes the actual probability density of the object for each area on the floor. Finally, ABP returns the top probability area(s) above its confidence, . This area(s) forms the result of localization.
4. Experiments and Implementation of Localization Algorithm
4.1 Our Choice of Algorithm
Distance Mapping Algorithm is simple and efficient in localization however it is not accurate and practical. It is because in real situation, the signal strength of an access point is not steady. It will fluctuate within a range. Therefore, the possible locations returned from one access point changes with time. By overlapping these area sets from all the access points, we can imagine that the resulting area is fluctuating. It indicates that the algorithm is very inaccurate.
Moreover, it is difficult to get a precise result from this algorithm. Sometimes, the overlapping area is an empty set (illustrated by Figure 4.1). And sometimes, a large area as the result set will be returned (illustrated by Figure
4.2).
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
In comparing the Simple Point Matching and the Area-Based Probability algorithm, ABP is a more mathematically approach than SPM since it introduces a Gaussian distribution modal and the Bayles rule to find out the probability. More importantly, ABP is more robust and accurate than SPM. In SPM, sets of areas are returned from each AP and they are equally important. The resulting area is formed by intersecting these sets. However, in ABP, if the signal strengths received from a particular access point is closer to its mean value, then it will return a higher probability. In other words, more accurate signals received from one AP can compensate for other inaccurate measurements from other APs. As a result, we have chosen ABP in our project of localization.
4.2 Applying the Area-Based Approach
In order to apply the area-based approach, we divide the whole 1st floor of the Ho Sin-Hang Engineering building into different areas. We count each room as a single area and we further divide the corridor into several areas. Figure 4.3 is the floor plan of the 1st floor of the engineering building.
Figure 4.3
For simplicity, we only choose 12 different areas on the 1st floor to apply the localization. Area 1 is the one near the lifts, area 2 is the one near the toilet, area 3 is the one in front of Rm101, area 4 is at the North-West corner of the corridor, area 5 is near the North-West stairway on the first floor, area 6 is the one in front of Rm117, area 7 is at North-East corner of the corridor, area 8 is near the North-East stairway, area 9 is the one in front of Rm121, area 10 is at South-East corner of the corridor, area 11 is near the door of Rm123 and area 12 is at Rm101.
4.3 Generating Training Set
We have implemented a program called Wi-Fi Location Detector. It is a powerful tool to measure the signal received from the access points. The detail of this program is in section 6.7.
At each area chosen, we measure the signal strength from the access points for 1 minute. The access points detected depends on the location of measurement. Then, we average the samples so that we get the training set.
Figure 4.4 summarizes the fingerprints at the 12 areas. The missing data entry represent the access point is undetectable at the corresponding position.
Position123456789101112AP MAC addressSignal Strength (dBm)00:02:2d:28:be:9e-70-62-58-67-73-78-83-86-84-81-78-5500:02:2d:28:be:5d-67-59-60-71-76-79-81-86-81-83-79-5200:60:1d:1e:43:9b-79-87-85-84-89-80-76-77-66-63-77-9000:0f:34:f3:60:40-63-69-65-74-76-72-77-84-76-74-66-7900:02:2d:21:39:1f0-82-78-82-59-78-73-83-85-8200:11:93:3d:6f:c00-90-85-86-89-8800:11:20:93:65:c00-89-89-9000:0f:34:bb:df:200-89-90-82-88-8800:0c:ce:21:1b:9d0-8700:0c:85:35:33:d20-88-8800:11:20:93:63:900-89-8800:0c:85:35:33:d40-8700:04:76:a7:ab:a3-90Figure 4.4
After getting the samples, we find out the standard derivations of each access point. They are ranged from 7-10. There are totally 13 access points that can be detected on the floor, however, we do not use all of them for localization. Some of the Wireless LAN access points are located on another floor of outside the engineering building, so only very weak signals can be collected from them. We then ignore these access points because they have the least contribution to localization and also the computation time of the Area-Based Probability algorithm can be shortened. Finally, we have chosen 7 access points listed in Figure 4.5.
Name of Access PointsMAC AddressVIEWTECH AP1000 ONE A00:02:2d:28:be:9eVIEWTECH AP1000 ONE B00:02:2d:28:be:5dCSWaveLAN00:60:1d:1e:43:9bqqqqq00:0f:34:f3:60:40CSWaveLAN00:02:2d:21:39:1fERGWAVE00:11:93:3d:6f:c0ERGWAVE00:0f:34:bb:df:20Figure 4.5
For missing signal strengths, we input -92 dBm as entry. We consider -92 dBm because it is slightly lower than the weakest signal strength we have recorded. Therefore, these values can also be used by localization algorithms in calculations. After the data-processing, the data are shown in Figure 4.6.
Position123456789101112AP MAC addressSignal Strength (dBm)00:02:2d:28:be:9e-70-62-58-67-73-78-83-86-84-81-78-5500:02:2d:28:be:5d-67-59-60-71-76-79-81-86-81-83-79-5200:60:1d:1e:43:9b-79-87-85-84-89-80-76-77-66-63-77-9000:0f:34:f3:60:40-63-69-65-74-76-72-77-84-76-74-66-7900:02:2d:21:39:1f-92-92-82-78-82-59-78-73-83-85-82-9200:11:93:3d:6f:c0-92-92-92-90-85-86-89-88-92-92-92-9200:0f:34:bb:df:20-92-92-92-89-90-82-88-88-92-92-92-92Figure 4.6
4.4 Method in Getting the Testing Set
The above data is the training set. Then the remaining step is to apply the Area-Based Probability algorithm to use the training set. Originally, we have implemented Wi-Fi Signal Scanner to collect the signal strengths manually and generate the training set. We then modify it to collect the signal strengths and generate a testing set from time to time. The following table is an example of a set of received signal strength (RRS) we get from Point 1, i.e., at the lift.
AP MAC addressSignal Strength(dBm)00:02:2d:28:be:9e-7100:02:2d:28:be:5d-7200:60:1d:1e:43:9b-8900:0f:34:f3:60:40-49Figure 4.7
From Figure 4.7, we can see that only 4 wireless LAN access points are detected. In order to complete and generate a testing set, we need to substitute a value of -92dBm for missing data of the remaining 3 wireless LAN access points. Then the resulting testing set is shown in Figure 4.8.
AP MAC addressSignal Strength(dBm)00:02:2d:28:be:9e-7100:02:2d:28:be:5d-7200:60:1d:1e:43:9b-8900:0f:34:f3:60:40-4900:02:2d:21:39:1f-9200:11:93:3d:6f:c0-9200:0f:34:bb:df:20-92Figure 4.8
In order to get a more general set of testing set, we will first collect 4 sets of signals before we apply the localization. Then, we generate the testing set by averaging the values of the 4 samples. Therefore, the default sample size of the testing set is 4.
We have collected 100 testing sets for each of the 12 locations and applied the localization. Therefore, there are totally 1200 test cases for our localization system. We will then use the result of these test cases to estimate the accuracy of our system.
We would also like to find out how the number of samples in a testing set will affect on the accuracy, so we need to get the testing sets with different sample sizes. In order to do so, we have modified the program in Wi-Fi Location Detector so that when we invoke the collection of signals once, the generated testing set will contain the average value of new and current signal strengths. In other words, we are able to generate a testing set with larger number of samples which should be more accurate.
4.5 Finding Probabilities at Locations
4.5.1 Applying Bayles Rule
With the testing set Sl, we need to calculate the probability of being at each location, Ai, on the floor given the testing set, i.e., P( Ai | Sl ). By using the Bayles rule
and the equation derived in Section 3.6 talking about the Area-Based Probability Algorithm,
,we know that we only need to calculate the probability of having the testing set Sl when having known the current location is at Li, i.e., P(Sl | Li) in the above equation (2) for all locations.
4.5.2 Finding the Probability P(slj | Ai)
P(slj | Ai) is the probability of having a signal strength of slj from APj given the location is at Ai. In order to find these probabilities, we need to use the assumption in Area-Based Probability algorithm. In ABP, signals received from different access points are assumed to be independent. For each wireless LAN access point, the sequence of received signal strengths sijk, k = 1 . . . oij , at each location in the original training set, T0, is modeled as a Gaussian distribution (or Normal distribution) .
The equation of Gaussian distribution is
,where is the mean and is the standard derivation.
In our application, we can take as the expected average signal strengths for the access point to be calculated. And in order to simplify the computation, we take as 8.5. x is the signal strength received from the access point in the testing set. Figure 4.9 shows the graph of an example with mean signal strength = -60dBm and standard derivation of 8.5.
Figure 4.9
However, there is still a problem. The equation is a continuous function, but the signal strengths received are discrete values ranged from 0 to -92. Therefore, in order to use the equation, we need to define an interval. The most appropriate interval is 1 because each signal strength value should have an interval of 1 in the function of Gaussian distribution. Therefore, the probabilities can be found by the following equation:
The probabilities found by integrating the Gaussian distribution equation can be illustrated by the Figure 4.10
Figure 4.10
For example, when the signal strength in the testing set from a particular access point is -50dBm, the probability is represented by the red shaped area in Figure 4.10.
A standard normal distribution is a kind of normal distribution having =1 and =1. An arbitrary normal distribution can be converted to a standard normal distribution by changing variables. We let z = (x-) / and so we get the following equation.
4.5.3 Finding Integral of the Gaussian distribution function
After that, we should introduce the error function erf(z) in probability. erf(z) is the "error function" encountered in integrating the normal distribution (which is a normalized form of the Gaussian function). It is an entire function defined by
We need to introduce the error function because it can calculate the integration of normal distribution function in terms of finite additions, subtractions and multiplications. To achieve this, we need another expression of erf(z) which can be defined as a Maclaurin series.
The relationship between the normal distribution function and the error function can be summarized by the following equations:
Hence, we can compute the value of this Maclaurin series and find out the probabilities P(slj | Ai) is the probability of having a signal strength of slj from APj given the location is at Ai for all i and j. We have found that if the value of signal strength is equal to the mean value of an access point, the probability calculated is approximately equal to 0.03.
4.5.4 Finding Probability P(St | Ai)
P(St | Ai) is the probability of having the testing set St when having known the current location is at Ai. So, we compute P(St | Ai) for all 12 locations by using the formula of independent event in probability:
P(St | Ai) = P(st1 | Ai) X P(st2 | Ai) X X P(stn | Ai)
Then, we calculate the probability density based on the assumption that the mobile device must be at one of the 12 locations, i.e., P(Ai | St) =1 for all locations i. We simply sum all the probabilities of the 12 locations and then divide all of them by the calculated sum.
With this formula derived in the algorithm,
Max{P(Ai |St) } = Max{c*P(St | Ai) } = Max{P(St | Ai) }
We return the area or location that is with the highest probability to indicate the mobile device is currently at this area.
SHAPE \* MERGEFORMAT
Figure 4.11 summarizes the key steps we use in localization
4.6 Experiment Result
The following 12 graphs show a general case that how the probabilities calculated by Area-Based Probability algorithm at the 12 areas change and achieve the goal of localization. Each of the graphs represents the Localization Graph at one area. There are totally 12 lines with different colors and each of them represent the probability of getting the testing set St given the location is at an area, i.e., P(St | A1), P(St | A2) P(St | A12). The testing set is generated by averaging the signal strengths in the samples. The x-axis indicates the number of samples being used in the testing set. More samples are collected as time goes by so the x-axis can also be interpreted as a timeline. The y-axis indicates the value in terms of probability which is ranged from 0 to 1.
In ABP localization, the area with highest probability is returned, which indicates the mobile device is location at this area. In other words, within the same number of samples, the area with probability represented by a point in its line on the top is the returned area. Therefore, for example, for the Localization Graph at Area 1, the correct result should be the deep blue on the top. Otherwise, it means the result returned is incorrect.
Figure 4.12
Area 1 is the one near the lift. From the graph, we can see that the deep blue line represents the probability of being at area 1. It shows the probability first starts at about 0.4 and then drops to 0.25 and finally it gradually increases to 0.33. The line is always on the top of other lines as the number of samples increases. Therefore, our system always indicates the object is at area 1 which is the correct result.
Figure 4.13
Area 2 is the one near the toilet. From the graph, we can see that the purple line representing the probability of being at area 2 is always on the top of other lines as the number of samples increases. The probability is stable and always stays around 0.5. For other probabilities, they are quite stable and always stay below a value of 0.2. Therefore, our system always indicates the object is at area 2 which is the correct result.
Figure 4.14
Area 3 is the corridor in front of Rm101. From the graph, we can see that the green line representing the probability of being at area 3 is always on the top of other lines as the number of samples increases. The probability is quite stable and is always around 0.5. For other probabilities, most of them are quite stable and all of them always stay below a value of 0.3. Therefore, our system always indicates the object is at area 3 which is the correct result.
Figure 4.15
Area 4 is the North-West corner of the corridor. From the graph, we can see that the light blue line representing the probability of being at area 4 is always on the top of other lines as the number of samples increases. The probability is quite stable and is always over 0.4. The probability of being at area 5 remains at a comparatively high value around 0.3. For other probabilities, they are quite low, stable and always stay below a value of 0.1. Therefore, our system always indicates the object is at area 4 which is the correct result.
Figure 4.16
Area 5 is near the North-West stairway on the first floor. From the graph, we can see that the deep purple line representing the probability of being at area 5 is always on the top of other lines as the number of samples increases. The probability is quite high and is always around 0.6. For other probabilities, they are quite stable and always stay below a value of 0.2. Therefore, our system always indicates the object is at area 5 which is the correct result.
Figure 4.17
Area 6 is the one in front of Rm117. From the graph, we can see that the brown line representing the probability of being at area 6 is always on the top of other lines as the number of samples increases. The probability is very high and is usually around 0.9. For other probabilities, they are very low, stable and always have a value near 0. Therefore, our system always indicates the object is at area 6 which is the correct result.
Figure 4.18
Area 7 is the North-East corner of the corridor. From the graph, we can see that the deep green line representing the probability of being at area 7 is below the blue one when the number of samples equals to 1. As the number of samples increases, the probability of deep green line increases and remains at a value of 0.36 while the probability of blue line drops and lies below it. Therefore, our system first indicates the object is at area 8 which is an incorrect result and then indicates the object is at area 7 when the number of samples reaches 5.
Figure 4.19
Area 8 is near the North-East stairway on the first floor. From the graph, we can see that the blue line representing the probability of being at area 8 is always on the top of other lines as the number of samples increases. The probability is quite high and is always around 0.45. The probability of being at area 7 remains at a comparatively high value over 0.3. For other probabilities, they are quite low, stable and always stay below a value of 0.12. Therefore, our system always indicates the object is at area 8 which is the correct result.
Figure 4.20
Area 9 is the area in front of Rm121. From the graph, we can see that the light blue line representing the probability of being at area 9 is below the deep green one when the number of samples equals to 1. As the number of samples increases, the probability of the light blue line increase and remains at a value over 0.35 while the probability of deep green line drops and lies below it. Therefore, our system first indicates the object is at area 7 which is an incorrect result and then indicates the object is at area 9 when the number of samples reaches about 5.
Figure 4.21
Area 10 is South-East corner of the corridor. From the graph, we can see that the pale blue line representing the probability of being at area 10 is below the light blue one when the number of samples equals to 1. As the number of samples increases, the probability of the pale blue line increase and remains at a value around 0.4 while the probability of light blue line drops and lies below it. Therefore, our system first indicates the object is at area 4 which is an incorrect result and then indicates the object is at area 10 when the number of samples reaches about 5.
Figure 4.22
Area 11 is the one near the door of Rm123. From the graph, we can see that the yellow line representing the probability of being at area 11 is always on the top of other lines as the number of samples increases. The probability is quite high and is always over 0.5. For other probabilities, they are quite low, stable and always stay below a value of 0.15. Therefore, our system always indicates the object is at area 11 which is the correct result.
Figure 4.23
Area 12 is at Rm101. From the graph, we can see that the orange line representing the probability of being at area 12 is always on the top of other lines as the number of samples increases. The probability is quite high and remains over 0.8 as the number of samples reaches 13. For other probabilities, they are quite low, stable and always stay below a value of 0.15 as the number of samples increases. Therefore, our system always indicates the object is at area 12 which is the correct result.
5. Analysis of Experiment Results
5.1 Performance of Area-Based Probability Algorithm
The performance of ABP algorithm is good. It usually returns the correct location with a high probability over 0.3 and for most of other locations, it usually return a probability as low as 0.001. Therefore, it works well in distinguishing different locations.
However, when two areas are close together, the signal strengths collected from one area is similar to that of the other. In this case, the algorithm usually returns comparable probabilities for these two areas. Therefore, the algorithm may fail to give the correct location.
There is a tradeoff between time and accuracy in localization. A testing set is usually more accurate if its sample size is larger, but it requires a longer time to collect the signals. ABP algorithm has an acceptable accuracy even though the sample sizes of the testing sets are small. In other words, ABP algorithm can be applied to some location-based applications which require real-time localization.
5.2 Accuracy of our localization system
Figure 5.1
Figure 5.1 shows the accuracy of our system at different locations. The accuracy is in terms of the percentage of our system returning a correct location during localization. We have taken 80 testing sets for each of the 12 locations and test on the result of our system. The overall accuracy of our system is about 75.94%. That means on average, our system can indicate 76 correct locations when taking 100 trials.
We have found that the accuracy varies with different locations. It is because the localization algorithm will depends on the testing set generated at different locations. The accuracy at area 9 is particularly low because the distance between area 9 and area 10 is too close. Therefore, the signal strengths received from area 9 is very similar to those from area 10. Hence, our system may fail to distinguish between the two locations.
5.3 The effect of number of samples on accuracy
Figure 5.2
Figure 5.3
Figure 5.4
Figure 5.2, Figure 5.3 and Figure 5.4 show how the accuracy changes with the number of samples included in a testing set. Figure 5.2 and Figure 5.3 show the accuracy changes at different locations while Figure 5.4 represents the overall accuracy change of the system. We can conclude that the accuracy increases with the sample size. It first increases significantly and finally levels off when the sample number equals 21.
The accuracy will never reach 100% because there are some other factors affecting the accuracy. It will be discussed in the next section.
5.4 Other factors affecting the accuracy
5.4.1 Hardware failure
When any of the access points fails to give out signals or give out signals at unusual strength, the signals received from the mobile device will be different. Therefore, the accuracy of the system will decrease.
5.4.2 Change in environment
When there is one or more access points in the floor, its signals will cause the disturbance for those of original access points. Also, when someone opens the door or change the location of some large enough objects in the floor, it will affect the signals received. Because the signals may be originally weaken by the doors or these objects.
5.4.3 Orientation in collecting signal
Figure 5.5
Figure 5.6
Figure 5.5 and Figure 5.6 show the accuracy of localization when using different orientation in collecting the signals. The accuracy is measured at Rm101 and the North-East Corner of the 1st floor corridor respectively. We can see that there are slightly differences in the accuracies for different orientations. The orientation in collecting signals has some but not significant effect on localization.
6. Center-of-Mass technique in Continuous Space Estimation
6.1 Limitation of Discrete Space Estimation
In the last semester, we have used the area-based probability model to find out the current location. This model bases on firstly finding out the probability of being at each location in the training set and then returning the one with the highest probability. We find out the result in this way is one of the methods in discrete space estimation in which only a fixed number of output can be returned.
However, this method of discrete space estimation is not suitable for some location-based mobile application. Because when we move between two locations in the training set, the algorithm will never return an intermediate location where is the actually position. In order to due with this limitation in discrete space estimation, we introduce the Center-of-Mass technique in continuous space estimation.
6.2 Center-of-Mass in Continuous Space Estimation
We have chosen to implement the Center-of-Mass technique in continuous space estimation to solve the limitation of discrete space estimation. Using continuous space estimation has several advantages including the possibility of returning intermediate positions, higher accuracy and more suitable for mobile applications. Therefore, in order to improve our tour guide application, it is necessary for us to introduce this technique.
The Center of Mass technique is based on treating each location in the radio map as an object in the physical space whose weight is equal to the normalized probability assigned by the discrete-space estimation process. We then obtain the Center of Mass of the N objects with the largest mass, where N is a parameter to the system. More formally, let p(i) be the probability of a location xi, i=1,2 n, where n is the total number of locations in training set. Let Y be the set of locations in 2D space and Y(i) is the corresponding position of xi
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
6.3 Applying Center of Mass technique in the Guide Service
In our Tour Guide Application, we have implemented the center of mass technique and we have found that it can really solve the limitation of the discrete space estimation. It can return an intermediate point, that is, points not in the training set. It also increases the overall accuracy and give a smooth change of position when we use a mobile device to move around the floor. The detailed evaluation of accuracy is given in later topics.
7. Evaluation of the Accuracy of Centre of Mass in Continuous Space Estimation
7.1 Methodology
As mentioned before, we have implemented the Center of Mass technique in our localization system. We are going to evaluate the performance of the new system and check if the accuracy is improved.
In order to find out the performance of our system and compared with the old one using Discrete Space Estimation, we carry out an experiment. Again, we have chosen 16 positions for the training set. They are shown in figure 7.1. In every location in the training set, we use our system to perform positioning for 100 times and we have implemented a simple program to record down the estimated positions. Our system estimates a new position at a interval of 4 second, therefore, totally, we need approximately 2 hours to get 1500 records.
After that, we calculate the distance error which is the distance between the actual position and the estimated positions. The value of the distance error is directly proportion to the actually distance. 1 distance error is about 10 centimeters. We also count the number of records that gives the same distance error for each location and it yields the frequency data.
Figure 7.1
7.2 Experiment Result
There are totally 15 positions for the training set. For each of them, there are two pairs of diagrams. One of them shows the distribution of the estimated points on the floor in which the blue dots on the floor plan represent the estimated point. The other shows the distribution of the distance error that is the distance between an estimated point and the actually position.
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
EMBED Excel.Chart.8 \s
The following figures show a summary of statistics at all the positions:
7.3 Analysis of Experiment Result
We have found that over 80% of the records are within 2 meters from the actually position and over 95% are within 3 meters. In other words, if the tolerance of error is 2 meters and 3 meters, the accuracy of our system is over 80% and 95% respectively.
For most of the locations, especially at location 4,location 5 and location 10, the curve in its distance error graph shifts towards the right. It indicates that all the estimated points contain a certain amount of error as noise. It is may be due to the error in collecting the training set and collecting data for the experiment. More likely, it is due to the inaccuracy of continuous space estimation because the distance in real world may not be proportion to the probabilities among the training set positions.
Take the following as an example:
Suppose there are two positions A and B. The distance between A and B is 5 meters. When we are exactly at position A, we collect a set of received signal strength at it and carry out continuous space estimation. Because the A and B is close to each other, the signal strengths in the training set at A and B can be similar. Therefore, the probability calculated at B is non-zero and significantly affect the estimated position. Hence, the estimated point is not at A but shift a little bit towards B.
SHAPE \* MERGEFORMAT
For all the locations, we can find a few estimated points with a large distance error, for example, those between 3 meters to 5 meters. These points contribute to the inaccuracy of our system. Since our application trigger continuous space estimation in real time (4 per second), the scanner in our system may not collect enough signal strength. With this limited number of received signals, it is not accurate to carry out space estimation and hence, the result is not desirable.
When we compare the continuous space estimation with the previously developed discrete space estimation, the result of former estimation at the training set locations is not precise enough. It is mainly due to the shifting effect in continuous space estimation. However, with an acceptable tolerance, the accuracy of the new system is still good. It has a better accuracy with tolerance of 2 meters.
For intermediate points which are those lying between training set positions, the discrete space estimation is unable to locate them. It can only at most accuracy return the closest training set positions. Therefore, it is meaningless to talk about its accuracy at these points. For continuous space estimation, we find that our system has similar accuracy for the intermediate points comparing to training set positions. Therefore, continuous space estimation is more suitable for our system.
8. Point Mapping technique in the Guide Service
8.1 The Aim of Point Mapping Technique
Although the Center of Mass technique works very well and improves the positioning accuracy, we still find there are some aliasing due to the computation. For some times, when we walk around the corridor, we can see the positions returned is inside a room which is incorrect. In order to remove this aliasing and give a more fancy output, we can use the point mapping technique to solve it. The goal of the point mapping technique is to map the position returned from the continuous space estimator to a nearest point in the corridor. Of course, for simplicity, we have assumed all the possible locations of the mobile device are within the corridor.
8.2 Applying Point Mapping Technique
There are several methods that can achieve point mapping algorithm. The simplest one is to divide the whole corridor into a set of points. And then, we search for the closest point in the set. But, this method will introduce new error from quantization and require a heavy overhead of searching. Therefore, we have decided to use a line as a unit. First of all, we divide the whole corridor on the floor into several line segments shown figure 8.1.
SHAPE \* MERGEFORMAT
Figure 8.1
In figure 8.1, there are totally 5 line segments and we denote them by L i for i=1,25. Then, we need to define each line segment L i by an equation:
P = P i1 + u i (P i2 P i1)
, where Pi1 (x i1,y i1) is the starting point of L i ,P i (x i2,y i2) is the end point of L i and u is a constant.
Suppose the point E(x e,y e) be the estimated point returned from the continuous space estimator. Let Ii be the point of intersection between one of the lines L i and the line at the tangent to L i passing through E. Their relationship is illustrated by the following diagram:
SHAPE \* MERGEFORMAT
After that, in order to find the closest point on the set of lines, we have to calculate the distance Di for all i, which is the distance between the estimated point E and Li.
Since the tangent is perpendicular to Li, we know that the dot product of the tangent and Li is 0, thus we have:
(E - Ii) dot (P i2 P i1) = 0
After solving this equation and make constant u as subject, we have
SHAPE \* MERGEFORMAT
Moreover, we substituting ui into the equation of Li gives the point of intersection Ii as:
x = xi1 + ui (xi2 xi1)y = yi1 + ui (yi2 yi1)
Having known the intersection, we calculate Di for all i which is equal to the distance between Ii and E given by:
||Ii E ||2
However, sometimes the intersecting point Ii does not line on the line segment Li, so we need to check the value of constant ui. Ii lies on the line segment Li if and only if ui lies between 0 and 1 inclusively. Finally, we return Ii with 0 d" ui d" 1 and with smallest Di.
SHAPE \* MERGEFORMAT
Figure 8.2
In figure 8.2, the point mapping technique maps the point at position 1 to position 2. Therefore, the new mapped position is along the corridor.
8.3 Evaluation of Point Mapping Technique in Continuous Space Estimation
In order to give a more fancy interface and outlook of our tour guide application, we have implemented a point mapping function in our system. The goal is to map the estimated point output from our continuous space estimator to the nearest point in the corridor. However, we do not know if this technique has any side effect in our localization accuracy. As a result, we introduce experiments to find out the effect.
8.3.1 Methodology
Again, we have chosen the 16 positions for the training set which are used in the continuous space estimation. They are shown in figure 7.1. In every location in the training set, we use our system to perform positioning with refinement of point mapping for 100 times. We also use a simple program to record the estimated positions. Our system estimates a new position at an interval of 4 seconds; therefore, totally, we need approximately 2 hours to get 1500 records.
After that, we calculate the distance error which is the distance between the actual position and the estimated positions. The value of the distance error is directly proportion to the actually distance. 1 distance error is about 10 centimeters. We also count the number of records that gives the same distance error for each location and it yields the frequency data.
8.3.2 Experiment Result
There are totally 15 positions for the training set. For each of them, there is a diagram shows the distribution of the estimated points on the floor in which the blue dots on the floor plan represent the estimated point with refinement. Finally, there are a summary of distance error of estimated point at all positions.
Position 0
Position 1
Position 2
Position 3
Position 4
Position 5
Position 6
Position 7
Position 8
Position 9
Position 10
Position 11
Position 12
Position 13
Position 14
Position 15
8.3.3 Summary of the Experiment Statistics
8.3.4 Analysis of Experiment Result
The performance of the Point Mapping algorithm is acceptable. It can achieve a better user interface for the Guide Service. In general, the estimated points with small distance error in continuous space estimation, the Point Mapping technique maps them to a point closer to the actual position. So, the overall distance error is reduced. On the other hand, for those with high distance error in continuous space estimation, the Point Mapping technique maps them to a point further away from the actual position. So, the overall distance error is increased. On average, the two effects cancel each other and hence the overall accuracy of our system is not affected by point mapping technique. To, conclude, it is feasible to use Point Mapping algorithm to give a fancy user interface.
9. Shortest Path Algorithm in the Guide Service
9.1 Introduction to Shortest Path Problem
Suppose the user want to go to a particular destination from the current location. The user may have more than one path to go through and we need to find a shortest path among all the possible paths.
For example, if the user is currently at Room101, and he/she wants to go to Room 117, it is very obvious that the user have 2 paths, one is through the upper red path in figure 9.1 and the other is through the blue path.
Figure 9.1
9.2 Applying Dijkstras algorithm in the Guide Service
Not all the people are able to read a map very clearly and some of them do know neither their current position nor their target destination even though given a map. Therefore, we have implemented an algorithm in our Tour Guide application in order to provide a shortest path for the user.
In order to teach the computer to find out the shortest path, we have used an algorithm called Dijkstras algorithm which is well-known to be a good algorithm to find a shortest path. However, we cannot apply the algorithm directly in our application. Firstly, we need to prepare a graph for computation. We define the nodes as the turning points or the ending of the corridors shown in figure 9.2. Then we add them to the graph. We also define edge between the nodes. If there is a path between two nodes, we add an edge connected between the two nodes. Also, we give a weight to each edge which is equal to the distance between the two connected nodes.
Figure 9.2
SHAPE \* MERGEFORMAT
Figure 9.3
In figure 9.3, we have converted the floor plan into a graph with 8 nodes. The weights of the edges are in the ratio of their distances between their two connected nodes.
Given the pre-defined graph as well as the source and destination location, we should add two more nodes, one for the source and the other for the destination to the graph. The most difficult part is to find a way to add the edges between the source or the destination and other nodes. First of all, we use the technique similar to the point mapping algorithm. We consider every edge as a line segment. The segment is defined by two points and their coordinates equal to the positions of the two connected nodes. Then, we find out the lines that the current or the destination is the closest to. After that, we are able to add the new edges and calculate their weight. Taking the same example, we have a newly constructed graph as figure 9.4.
SHAPE \* MERGEFORMAT
Figure 9.4
A shortest path problem is given a connected graph G=(V,E), a weight d:E->R+ and a fixed vertex s in V, find a shortest path from s to each vertex v in V. In our case, V= {1,2,3,4,5,6,7,8,C,D} and E= {(1,2), (2,C), (C,3), (3,8), (3,4), (2,D), (D,6), (5,6), (6,7), (4,7)} and their weight are shown in figure **. C is a vertex representing the current position and D represents the destination.
With this graph, we are able to find out the shortest path from C to D. In Dijkstras algorithm, there are totally |V|-1 times of relaxation. Initially, the shortest distances L(V) to all the vertexes are infinity and the set S contain the source C only. In each relaxation, the value L(V) is recalculated if V is not in S and connected some V in S. After each relaxation, a new vertex with minimum L(V) is put to a set S until all V are in S.
9.3 Pseudo code of Dijkstra's Algorithm
Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2.
For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
Let Si+1 = Si cup {ui+1}.
Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.
9.4 Example of Dijkstras Algorithm
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
SHAPE \* MERGEFORMAT
10. Multimedia Guidance System
10.1 Introduction
Multimedia Guidance System (MGS) aims to develop Location-Based Multimedia System in a short time. With these tools, non-professionals can develop with little effort. With tradition development methods, it includes lots of steps such as design, analysis, etc. MGS simplifies steps and increases the efficiency and productivity in implementing system.
MGS consists of three components: Wi-Fi Signal Scanner (WSS), Multimedia Guidance Processor (MGP) and Location-Based Multimedia Service System (LBMSS).
Wi-Fi Signal Scanner
This is a tool installed in a mobile device to collect the data from access points at target place. It records the mean of signal strength received by the mobile device. After collecting the data from all the target position, the data is then being analyzed in the MGP.
Multimedia Guidance Processor
Multimedia Guidance Processor (MGP) is a tool to process signal strength data and set the client environment for LBMSS. MGP have to filter out some signal strength data because noise data are collected from WSS. This step can increase computation in LBMSS. For each target position, specific information is also set in MGP, e.g. name, picture, video, etc. Finally, LBSData file will be generated by MGP and passes to LBMSS for setting client environment.
Location-Based Multimedia Service System
Location-Based Multimedia Service System (LBMSS) is main part of MGS. This part composes of clients and servers. The client environment is controlled by LBSData file which is generated by MGP. The servers are mainly constructed by existing server architecture (e.g. HTTP, FTP). Some servers are tailored made for specific multimedia services. With client and servers, LBMSS provides interactive multimedia service for users. LBMSS provides chat, video, paint and guide services.
10.2 Deploying Procedure
SHAPE \* MERGEFORMAT
Figure 10.1
Step 1 (Collecting Data):
First, the developer needs to collect the source data from the Wi-Fi network at target place. At each target position, it must collect mean strength signal data from Access Points. The data then are processed in the next step and used in localization algorithm.
Step 2 (Processing Data and generating LBSData):
Second, there are two things to do in this step:
1. The developer needs to process the source data and filter out some useless data (noise data). Normally, WSS collects some weak signal from outside target place or failed Access Point. This noise data affects the accuracy of localization algorithm. The data must be filtered out manually.
2. The actual position on map picture, name, video and picture of the position will be shown in LBMSS. All information should be set in this step.
At the end, LBSData file is generated by MGP.
Step 3 (Deploying System with clients and server application):
LBSData file generated in step2 would be used by LBMSS client. The client will set environment according to LBSData File. The client application estimates actual position by localization algorithm. The server applications environment is also be set manually in this step. It includes setting up server, testing server and deploying server. After setting clients and servers, LBMSS can deploy multimedia service to users.
10.3 Features of Multimedia Guidance System (MGS):
a. Scalability:
The MGS can apply in any flexible environment. In case the change of environment, it can generate the System with perform the procedure once. The new System can be run in the new environment. MGS can be scaled at any time and anywhere.
b. Abstraction
The MGS would do all the prepared work for the developer. And most of prepared work is only the low level technology studying and research work. The developer only focuses on how to increase the accuracy of System rather than studying the prepared work. The prepared work is transparent for the developer.
c. Transparent
No matter what changes in the MGS, they can still deploying the system without any problem. Even though the core part of the MGS system is changed, it only affects core part, such as algorithm. The data source remains unchanged in the MGS.
d. User-friendly
The three components are made by using fancy user interface. They are very easy to use. The developer only needs to know how to use them correctly. It can be used by anyone with basic computer knowledge. They can handle the MGS well.
The MGS is a powerful and user friendly system. It can re-deploy system with applying three components once. The new system can deploy to users. MGS can develop Location-based Multimedia Service System within a short period of time.
10.4 Wi-Fi Signal Scanner (WSS)
Wi-Fi Signal Scanner is a tool to collect the signal strength received at the target position. The data then are used in the MGP. We will detail explain the WSSs architecture, method of usage in the following section.
10.4.1 Software Architecture
SHAPE \* MERGEFORMAT
Figure 10.2
The Software Architecture is divided into two main parts: Control Architecture and View Architecture.
Control Architecture (CA) controls the program flow in the WSS. Its main function is to get the Wi-Fi information for the program. CA is made by tools Embedded Visual C++. Embedded Visual C++ supports lots of libraries for programming Pocket PC. It is a desirable tool for CA. The CA gets the Wi-Fi information though Network Driver Interface Specification (NDIS) Application Programming Interface (API). NDIS is explained in the following section.
View Architecture (VA) is used to display the result for WSS. Since the Visual Studio .NET 2003 supports lots of user interface control, it is desirable for building a fancy interface for WSS. Many fancy user interface controls are supported, such as Data Grid, Label, Tree View and Scroll Bar.
The main bridge for VA and CA is the Dynamic link library (DLL). The CA information is passed by the DLL to VA such that it can display in the VA interface. The CA project is build by Dynamic link library (DLL) project in Embedded Visual C++. The main DLL role is to act as a bridge for CA and VA to communicate. This is an important part of Software Architecture.
10.4.2 Network Driver Interface Specification (NDIS)
The Network Driver Interface Specification (NDIS) is the interface by one or more network adapter drivers communicate with network adapters, protocol drivers, miniport drivers, and operating system. NDIS is abstracted all the lower level network adapter development for developer.
NDIS provides a pair of abstraction layers that connect network adapter drivers to an overlying protocol stack. Transmission Control Protocol/Internet Protocol (TCP/IP) and Infrared Data Association (IrDA) are the example for overlying protocol.
NDIS is supported in the Windows CE. NDIS provided a abstracted programming interface to write an target-specific programming/driver for the network adapter. All Kernel-mode functions required for development can be exported by NDIS Dynamic Link Library (Ndis.dll). NDIS also store the state information for the network adapter. That means all the information related to network adapter can be access by the user program through NDIS.
NDIS support these following functions:
a. A network adapter driver provided an abstracted layer for the upper-layer (Application Layer) to sending the data into the network.
b. A network adapter driver provided an abstracted layer for the upper-layer (Application Layer) to receive the data from the network.
c. It provides an interface for upper-layer (Application Layer) to configure a network adapter or a network adapter driver
d. It provides an interface for upper-layer (Application Layer) to queries a network adapter driver for specific configuration data from an underlying network adapter or from the network adapter driver
The following diagram shows the overall NDIS architecture for Windows based Architecture:
Figure 10.3
This diagram shows the NDIS acts as the bridge for the Protocol and the network adapter (Lower Layer). NDIS acts as midpoint role for the application to communicate with network driver. NDIS is interface for the application to get the lower layer information in the network adapter.
10.4.3 Feature of Wi-Fi Signal Scanner
Figure 10.4
The above is the View of the WSS. They are made by the fancy user interface by Visual Studio .NET 2003. They are mainly made by Data Grid, Menu Item, etc. WSS is a highly user friendly software. The developer can learn the software in a short period of time.
There is much information shown in the WSS:
MAC Address:
It is the MAC Address of Access Point.
SSID:
It is the SSID of Access Point. Most of SSID is broadcast by the Access Point. SSID is not secured in WLAN.
WEP:
It is shown whether the WEP is enabled in the Access Point.
RSSI:
The signal is received by the mobile device for that particular Access Point
Num:
The number of times that signal received by the mobile device
Total:
The total number of signal strength received by mobile device.
Mean:
The mean of signal strength is received by the mobile device for that particular Access Point. The mean would used in localization algorithm.
There are several functions in the WSS:
Figure 10.5
Start:
It is to start the timer of WSS. The time is enabled initially.
Stop:
It is to stop the timer of WSS.
Clear List:
It is to clear the current in the Data Grid.
Save Log:
It is to store the Wi-Fi information in the Data Grid. The Log file is stored the same path as the WSS program.
Exit:
It is to exit the WSS.
In the Timer Menu, there is setting option. It is to set timer value in WSS.
10.4.4 Collecting Data Procedure using Wi-Fi Signal Scanner
SHAPE \* MERGEFORMAT
The above flow diagram shows the common procedures of collecting the source data in one target position. They are divided into five main states. Two main states are important in collecting data. They include Analysis the collected data and Start / Stop timer.
Analysis the collected data:
In collecting the data in target place, some weak signals are received by device. They mainly come from other building, broken-down Access Point, etc. If there are too many weak signals in the collected data, it should be re-collected. The details would be explained in the following section.
Start / Stop timer:
WSS provides the flexibility for the developer to analysis data by stopping timer. It is convenient for them to analyze data in the middle of collecting process. If mean signal of target position tends to be static in short period of time, the developer should stop the timer and collect data in other target position.
10.4.5 Analysis the Data in Wi-Fi Signal Scanner
Figure 10.6
The above is the data got by the WSS at one target position. There is different meaning in each type of data. There are explanations in the following:
RSSI:
The signal is received by the mobile device. If RSSI shows a null, it means that no signal is received by the mobile device. Normally, RSSI shows the negative number. The value is the signal strength of that Access Point received by the device. The larger value (smaller in magnitude) means that signal strength is stronger for that Access Point. The value of RSSI is in terms of dBm.
Num:
It shows the number of signal received by device. If value of Num is too small, it means the connection between Access Point and device is very weak. We may ignore this data in localization algorithm. The data is labeled as noise data. This data is useless in locate the position. The data need to be filtered out in the MGP.
Mean:
This is an important data in the MGS. It is used in the localization algorithm. This mean data normally tends to be static after one to two minutes. If the mean data fluctuates for a long time, it means that signal received by device is not stable. This data should also be ignored because it would affect the accuracy of MGS. In localization algorithm, the stability of mean signal is very important. It should be very careful to analyze the data in WSS.
Total:
It is the same meaning as the Mean. It can be used to analysis the quality of signal strength with num. If num is very small and total is large, it means the quality is very poor. If num is very small and total is small, it means the quality is very good. The Total normally is used to calculate the Mean.
To conclude, it is important for us to analyze source data. It would affect the accuracy of localization algorithm. It should be careful when collecting the data in target position. There are different kinds of meaning for each field in the WSS. This would help the developer to filter out the noise data in the MGP.
10.5 Multimedia Guidance Processor (MGP)
Multimedia Guidance Processor (MGP) is a tool to process the signal strength data that are collected by WSS. After analyzing the data, we need to filter out some noise data if needed. The Location-Based Multimedia Service System (LBMSS) client environment is also set in the MGP. The developer need to process all the data and set client environment in MGP.
10.5.1 Overview of MGP
Figure 10.7
MGP is mainly divided into 3 main regions: Position, Access Point, Setting and Information.
Position:
It shows the number of target position added in MGP. The default name of newly added position is positionX (where X is any integer). After setting data for particular position, there would be a list of Access Point under that particular position.
Access Point
It shows the total list of Access Point being used in the MGP. The list is the Media Access Control (MAC) Address of Access Point. And it can be delete the items in list whenever is needed. The change of Access Point is also updated in the Position region.
Setting and Information:
The name, data, video, picture and point of position are set in this region. If parameters are not set in MGP, they are set to default value. The Set Line button is to set lines for point mapping algorithm. The lines are used to map points in point mapping algorithm.
In the middle part, there are three services available in mobile client. Due to different requirement of system, it should be selected appropriate service for mobile client. If all service checkbox are clicked, all services are available in mobile client.
At the bottom of region, it shows the information of particular region. By clicking the list in the position region, the most updated information of selected position will be displayed here.
10.5.2 Data Processing Procedure in MGP
SHAPE \* MERGEFORMAT
Figure 10.8
There are eight steps to process data in MGP.
Step 1(Open MPG)
First, open the MGP program and process data step by step.
Step 2(Set the Project Name, Server Path and Map Picture Path in Setting)
First, we should click File menu and Setting option. The setting dialog will appear immediately.
Figure 10.9
Figure 10.10
There are six fields in setting dialog. They are Project name, Media server, Picture Server, Paint Server, Central Server and Map Path. These fields control the client environment. If any fields set incorrectly, the client program cannot be run.
Step 3 (Setting Lines)
Figure 10.11
First, we load Set Line Dialog by click Set Line button. We can add line by click start position and end position on the map. Line will be shown on the map and a new item also is added in line list. By click item on the list, corresponding line will be shown in red colour. When we draw line wrongly, we can delete it by selecting on the list and click Delete button.
Step 4 (Add/Delete the target Position)
Figure 10.12
When adding or deleting the position, it should click the Position Menu in the Menu Bar. After adding the position, a new position is added in the list. The default name is PositionX. (where X is an integer)
Figure 10.13
Step 5 (Set the name, data, video, picture and position in the Map Picture)
We should set the name, data, video, picture and position in the Map Picture for each position.
Figure 10.14
After clicking Set Point, MapBoard is shown immediately. We can set the point on the Map Picture by clicking on the Map.
Figure 10.15
We set the name of a position by click the Set Name button. We should input the name in the Set Name dialog.
Figure 10.16
We set the picture of a position by click the Set Picture button. We should input the picture name which locates in Media Server.
Figure 10.17
We set the video of a position by click the Set Video button. The Video will be played when user is at that position.
Finally, we should set source data (signal strength data) to each position. These data will be used by localization algorithm. Source data are import from WSS to MGP. After setting the Data, there would be a list of Access Point under the name of position in the position region.
Figure 10.18
We also need to set Point of interest for Guide Service.
Figure 10.19
First, we have to click Add POI in Position Menu. The MapPOI Dialog will be shown immediately.
Figure 10.20
It can add Point of Interest (POI) by click on the map. The default name of POI is POI + . We can change the name by Set Name button with name inputted in textbox. If we want to delete POI, we can select POI in list box and click delete button.
After finishing adding POI, we have to go to next step.
Step 6 (Filter the noise data)
Figure 10.21
After analyzing the source data, we may need to filter out some noise data. It is done by deleting item in the Access Point List. The access point listed in the position would also be updated.
Step 7 (Select service for mobile client)
Figure 10.22
Then we select suitable services for client. We can select them by clicking checkboxes.
Step 8 (Generate Location-based Data)
Figure 10.23
After processing the source data, we can generate the Location-Based Data (LBSData) File by clicking Generate in File Menu. If all settings are set correctly, Generate successfully message box will be shown. Otherwise, error message will be raise.
10.5.3 Feature of Multimedia Guidance Processor
Fancy User Interface:
The MGP is made Visual Studio .NET 2003. Graphics User Interface (GUI) simplifies the complexity of using MGP. The user can learn MGP in a short period of time. The user can set the Position parameters by just click the buttons or Map Picture in the interface. It is convenient for user to process the data in MGP.
Abstraction:
The MGP provides abstraction for the users to hidden the complex format of LBSData. They only to set the Data by GUI interface and MGP then generate LBSData for user. Whenever the format of LBSData changed, the MGP dont change except the Generating part. MGP abstracts all the core part in MGS.
Robustness:
There is an error handling in MGP. Whenever error occurs, error message would be shown on the screen immediately. This is to prevent the System crash in MGP when generating LBSData. It is an important feature in MGP. This is to ensure the LBSData generating successfully.
Figure 10.24
Flexible
MGP is a flexible system. The user can set the position parameter according to the user need. There is no restriction on setting the parameters. The user can set the parameter freely. The Add/Delete Position Option can let the user to add or delete position in the MGP. This option provides another flexible for user.
10.6 Location-Based Multimedia Service System (LBMSS)
Location-Based Multimedia Service System (LBMSS) is a system to provide multimedia service to clients based on location detected. The system provides chat, paint and video service. The clients use service through networking. The corresponding service output (e.g. picture) would show on the client devices screen. The detail would be described in the followings.
10.6.1 System architecture
EMBED Visio.Drawing.11
Figure 10.25
Location-Based Multimedia Service System (LBMSS) is consisting of Chat Server, Paint Server, Media Server and Mobile Clients. They are connected by Wireless Local Area Network (WLAN). Each Server provides different kinds of multimedia service for clients. The detail will be explained one by one as follow.
10.6.2 Paint Server
Paint server provides print server services for client. After clients draw their own picture, they can send it back to paint server. The server can print their artwork for clients whenever they needs.
The Paint Server divided into 3 modes: Signature, Points and Management.
Signature Modes
Figure 10.26
In the Signature mode, it show the latest artwork send by the client. The artwork includes two components. They are drawing lines and background picture. The client first captures drawing line and encode into byte stream. Then client sends encoded byte stream together with background picture path to server. After server receives message from client, it process message and draws the artwork on screen and save it on server storage immediately. The artwork can be printed by clicking print button if needed.
Points Mode
Figure 10.27
The Points mode shows line information. It mainly uses as debugging. In this mode, it shows number of drawing lines in the artwork and the point information in each line segment including point coordinates and number of points in each segment. This information is to check whether client program capture the correct line information. Also, it is used to verify the correctness of the message. If received message is corrupted, it shows strange code on the screen. This is to check the correctness of received message.
Management Mode
Figure 10.28
This mode is to manage all artworks received by server. Server sometimes may receive many artworks in a short time. The screen may refresh very fast and server cannot print the artwork one by one. However, server saves artwork in the storage whenever receives any incoming message. The saved artwork can be found in the Management mode. The server will save artwork in the following format:
+