2
5
4
6
8
9
1
3
7
Encounter
2
5
4
6
8
9
1
3
7
Non-encounter
t
1
t
2
(a) (b)
A’s potential location
B’s potential location
C’s potential location
A’s ground truth
B’s ground truth
C’s ground truth
Figure 2: Examples illustrating utilization of en-
counter and non-encounter
Here, we emphasize that intersecting potential location
sets for encountered users do not always result in one spe-
cific location. Depending on the localization accuracy of
the underlying localization system, it may contain no or
multiple locations. This motivates us to design a proba-
bilistic approach of utilizing users encounter information in
Section 3.2.
2.2 Utilizing Non-Encounter Information
In contrast to encountering other users, it is more common
for a user not to encounter other users over a period of time.
Interestingly, in this work we reveal that such non-encounter
information can also improve localization accuracy.
The most intuitive method to utilize non-en counter in-
formation is to remove overlapping elements from potential
location sets of non-en countered users. For example, as-
sume the potential location set for user A and user B is
P
A
= {1, 4, 6} and P
B
= {2, 5, 6}, respectively. If user A
does not encounter user B we can remove the overlapping
location P
A
T
P
B
= {6} from both P
A
and P
B
. However,
this intuitive approach to utilize non-encounter in formation
is incorrect. For example, user A may actually locate at lo-
cation 6, while user B locates at location 5. Even though
they do not encounter each other, we cannot simply remove
the overlapping elements from t heir potential location sets.
To illustrate the main idea of how t o effectively utilize
non-encounter information, we use the ex ample shown in
Figure 2(b). The potential location set generated by the
underlying in door localization scheme for each user A, B and
C is P
A
= {1, 5}, P
B
= {5, 7} and P
C
= {5, 7} respectively.
Users B and C do not encounter each other, but they both
potentially locate at location 5 or 7. Therefore, we can infer
that there is exactly one user locating at each location 5 and
7, but we can not distinguish whether it is user B or user
C. Furthermore, since user A also encounters n either user
B nor user C, we are certain that user A does not locate at
location 5 or 7. Otherwise, user A would have encountered
either user B or C. Consequently, user A can be localized
to location 1 by removing the impossible location 5.
To generalize the above inference process, let us assume
that there are n users who do not encounter each other, and
their estimated potential location set at current time t is
P
1
(t), P
2
(t), . . . , P
n
(t). If we have
|P
1
(t)
S
P
2
(t)
S
· · ·
S
P
n
(t)| = n,
(2)
then we can infer there is exactly one user at each of these
n locations. For such a set of n users, we call them n-Total
Occupancy Set (n-TOS). Take the example shown in Fig-
ure 2(b): users B and C form a 2-TOS since |P
B
S
P
C
| = 2.
Furthermore, for a given number n, there may exist multiple
n-TOS involving different n users in th e system.
A’s potential location
2
5
4
6
8
9
1
3
7
Encounter but
no overlap
2
5
4
6
8
9
1
3
7
Non-encounter
with false TOS
B’s potential location
C’s potential location
A’s ground truth
B’s ground truth
C’s ground truth
(a) (b)
User A and User B
form a 2-TOS
User C is wrongly
localized
Figure 3: Examples illustrating problems of deter-
ministically utilizing encounter and non-encounter
Therefore, to fully utilize non-encounter information, as-
suming there are currently n users in the system, we need
to first find all existing total occupancy sets such as 1-TOS,
2-TOS and so on, up to n-TOS at time t. Given a specific
i-TOS, where i = 1, 2, . . . , n, let the un ions of all potential
location sets for these i users be U
i
. For each user j in the
system who does not encounter any of the i users in this
sp ecific i-TOS at time t, we can update his or h er potential
location set as follows:
P
j
(t) = P
j
(t) − P
j
(t)
T
U
i
(3)
Clearly, in this way, we improve the accuracy of the lo-
calization by effectively removing the impossible locations
from the potential location sets of individ ual users. While
utilizing TOS effectively improves the performance of indoor
localization systems, we observe it is not trivial to find all
TOSes in the system. In fact, we have proven t his problem
is NP-Complete. In Section 4, we show it is not necessary to
find all TOSes in p ractical systems and discuss how to find
useful TOS es in detail.
3. ADVANCED DESIGN
In Section 2, we introdu ce the main idea of our Social-
Loc design in a deterministic manner to remove impossible
potential locations. H owever, such a deterministic approach
is error-prone if the original potential location sets or so-
cial sensing services contain errors. In this section, we first
discuss the limitations of the deterministic approach with
several examples and then extend the basic design to prob-
abilistic approaches.
3.1 Limitations of the Basic Design
If the ground truth locations of mobile users are always
included in their potential location sets generated by the un-
derlying localization system, Social-Loc can effectively apply
the deterministic method introduced in the prev ious section
to imp rove the localization accuracy. However, due to var-
ious measurement and estimation errors (e.g., drift errors
from inertial sensing), the estimated potential location sets
from the underlying localization system may not even con-
tain the ground truth locations of mobile users [28]. Under
such scenarios, if we just directly apply the deterministic
Social-Loc design, we may obt ain very limited performance
gain or even performance deterioration.
For example, as shown in Figure 3(a), user A and user
B encounter each other at location 5, and their potential
location sets
1
are P
B
= {1, 2, 4} and P
A
= {3, 5, 9} respec-
tively. However P
A
∩ P
B
= ∅, then we can easily infer that
the potential location set for user A or user B contains the
error, but we can not further identify which user’s potential
location set contains error. To make the case even worse, if
剩余13页未读，继续阅读
weixin_38732315
- 粉丝: 7
- 资源: 963
我的内容管理
展开
最新资源
- 十种常见电感线圈电感量计算公式详解
- 军用车辆：CAN总线的集成与优势
- CAN总线在汽车智能换档系统中的作用与实现
- CAN总线数据超载问题及解决策略
- 汽车车身系统CAN总线设计与应用
- SAP企业需求深度剖析：财务会计与供应链的关键流程与改进策略
- CAN总线在发动机电控系统中的通信设计实践
- Spring与iBATIS整合：快速开发与比较分析
- CAN总线驱动的整车管理系统硬件设计详解
- CAN总线通讯智能节点设计与实现
- DSP实现电动汽车CAN总线通讯技术
- CAN协议网关设计：自动位速率检测与互连
- Xcode免证书调试iPad程序开发指南
- 分布式数据库查询优化算法探讨
- Win7安装VC++6.0完全指南：解决兼容性与Office冲突
- MFC实现学生信息管理系统：登录与数据库操作
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
