英语原文共 23 页，剩余内容已隐藏，支付完成后下载完整资料
图七(a)使用安装在窗户上的光线传感器来推断窗户的方向的算法准确性
(b)使用算法来推断大多数没有北面窗户的窗户方向的准确性
我们采取三种方法来减轻环境因素对光线传感器读数的影响。第一，我们把周围的环境光传感器放置在门口来减轻来自于隔壁房间的对光检测，通过把一个传感器指向每个相邻的房间，和其它门口的传感器一起集成到同一个外壳内。第二，所使用的阈值，以确保一个窗口是否存在由每个通道的磁力计读数确定，这指示了光传感器的方向。例如，直接朝向东方的光传感器会对来自东窗口的光更为敏感，并对从任何其他方向上来的光不敏感。第三，我们假设一个窗口上不能和室内门道在同一侧存在。例如，如果内部门道是在室内的南侧墙面，那么房间里不太可能有一个窗口在南墙上，因为另一个房间在南墙后。表7（b）表示使用由门道光传感器观测到的光图案对窗口的方向的推断并把他和每幢房子每个房间的窗口实际朝向做了对比。在A,E,F房子里，只有朝北方向开的窗户被门口的光传感器错过了。而对于G房子，只有三个朝向南面的窗子被检测到了。如果在同一面墙上有超过一扇的窗户，它们会被认为是同一个窗户。
表三 基于是否存在光线传感器和磁力计和它们的方位的方案
|
Scenarios |
Light Sensor Position |
Magnetometer Position |
|
Scenario-1 |
Window |
None |
|
Scenario-2 |
None |
Doorway |
|
Scenario-3 |
Window |
Doorway |
|
Scenario-4 |
Doorway |
Doorway |
7.搜索楼层平面图的空间
我们的搜索算法的目标是要产生一组最和用我们的传感器推测到的结构约束一致的平面图。搜索算法的输入是房数R， Rtimes;R的邻接矩阵表示了房间的周围，和门或窗方向的角度。该算法的输出是一个确定的以（X，Y）为每间客房坐标的拓扑结构。
7.1定义搜索空间
首先，我们定义搜索空间。我们用图A,B,D房子的图8来说明使用该搜索空间的每个阶段。如图8（c），8（i），和图8（o）中所示，每个房子搜索数的根是邻接矩阵，这是从在先前执行的一步中的传感器阵衍生出来的。搜索树的第二级是一组所有可能的门道分配，其中每个定义不同的一组对每个出入口的方向。图8（d）中，8条（j）及图8（p）的显示每个房子的正确的门道分配。对于每对相邻的房间，每个门口有四种可能的方向（北，南，东，西）。因此，门道分配的总数目是4D，其中D是门道的数目。对于每个门道分配，搜索算法探讨所有可能的内墙分配。这些作业定义任何一对房间是否和一个内壁相邻(但不是门口)。图8（e），图8（k）和8（q）的显示每间房子的正确门道分配。任何一对不和门道连接的房间都可能通过内壁相邻，并且这样的房间对的总数为。最后，给定一组门道壁分配和内壁分配，我们可以通过创建一个线性项目来得到每个墙壁的大小，这个线性项目使每个墙壁的长度Li 和i满足和：adjacent()和这个限制。一旦墙壁的大小确定了,计算机算法就会以一序列的形式把房间排列起来以产生每个房间坐标(x，y)。
7.2减少搜索空间
图八 图八显示了我们算法的每一步骤：（1）基于更小的活动范围，传感器们被聚集在一起，(2)这些集合被放在房间里或者房间之间的相邻之处，(3)门道被分配给了特定的墙壁(N,S,E,W),（4）房间之间定义的相邻的内墙，(5)楼层的空间布局。
表IV 比较不同的结构限制对算法准确性的影响，此表显示了只有在窗户上装有光线传感器(方案一)的效果，只有在门道上装有磁力计的效果(方案二)，以及都装的效果(方案三)。搜索面积的总面积是非常大的(第二排)。利用结构限制可以减少搜索面积(第三排到第四排)。一开始每幢房子搜索空间的大小是不一样的，导致总共的搜索面积太大。合理的拓扑结构总数是，其中，D是门道的数量，是通过内壁相连的房间对的数量， 数字4表示了两个房间连接有四个可能的方向。的最大可能数值是。在表IV和表V中的第二排陈列了用刚才给的方程计算的每个房子的总共空间大小。表IV和V显示，在表III不同的方案下，该搜索算法不同阶段得出的搜索空间的大小出不同的方案。表IV和V分别比较方案1，2，3和方案2，3，4。前三个方案在表IV中用于基于窗户，门道和相对方向的知识的搜索精度的对比。正如表IV的最后一排所示，如果运用方案3中窗户和门道的方向，我么你可以得到最小的候选面积，门道的方向(方案2)会比窗户的方向(方案1)有用的多。因此，在表v中，比较基于表III方案2，3，4减少的搜索面积，在所有的方案中，所用到的门道的方向都来自于磁强计,并且我们只改变了光敏器件的位置。在 表v中的最后结果显示，在没有光传感器的情况下，即使使用最简便的方案（方案2） 也没有在很大程度下影响准确度。为了有效的搜索每一层的空间，使用三种不同的排除技术。本节将论述第一种技术，另外两种技术将在7.3 节论述。首先，如若窗户和门道的方向已经知道的话，就不用考虑和这些方向不一致的拓扑结构了。也就是说，如果一个门道的方向已经确定是南北朝向，就不用考虑将门道放在房间的东方或者西方的墙壁上的拓扑结构了。正如表iv和表v的第三排所示，知道了门道的方向可以将门道的搜索空间从减少到。在以前的研究上对精确度的提高和搜索面积的减少可以通过运动传感器的方向来实现。因为运动传感器被放在和磁强计同一个地方了，它们相对于门道的方向是已知的。正如表iv和表v所示，一个在南北方向的门道上的运动传感器(和安装这个运动传感器的房间)既不在东边的或者西边方向的门道上。这确保了门道的搜索空间从到1。同样的，如果一个窗户相对一个房间的方向是已知的话，我们就不用考虑相同方向有门道的房间了。所以，如表IV的第三排所示，提前利用如上文所述的排除技术，利用方案1所得到的窗口方向减少了2到4个数量级的搜索空间。在第三排在方案2下门道的约束使其减少了2到3个数量级，在方案二下第四排的运动传感器的方向约束使其减少了3到7个数量级，正如我们在两个表中看到的一样。如果同时增加窗户和门道方向的限制(方案3，第三排)比单独知道门道的方向使搜索空间的大小减少4个数量级，在这里，窗户的约
表V 比较光线传感器安装在不同位置时对算法准确性的影响，表格显示了没有光线传感器(方案2)，在窗户上安装光线传感器(方案3)，在门道上安装光线传感器(方案4)对减少搜索空间的效果，表格显示了在门道上安装光线传感器是和限制窗户的拓扑位置对减少搜索面积的效果是一样的。
束是移除不符合条件的门道方向的情况的，反之亦然，用运动传感器的方向也移除了条件不符的门道方向的情况。所以如果同时使用运动传感器和窗户方向的限制不能叠加。
7.3 有效的搜索空间
排除技术仅仅将搜索的节点减少到了百万和千万的数量级上。这在计算上易于处理，但在搜索的精确度上确差强人意。在这节里所论述到的删减技术依赖于我们分配每个节点一个非单调递增的函数基于这个函数，我们使用传统的alpha;minus;beta;的排除技术:一旦一个数值低的叶节点被检测到了，搜索程序就不会再搜索有一个高数值的根的子树。我们也利用数值函数来提前结束搜索:当搜索树的底部时，如果搜索程序检测到额外添加的内墙增加了一个节点的数值的话，则终止或者回溯。这种排除技术是基于子树已经超出了约束的观察上的。第五排展示了内墙分配的数量其实是在下文所论述的基于单调递增函数的alpha;minus;beta;的排除技术之后所探讨的。我们需要利用结构限制从百万或数十亿的可能的拓扑结构中选出最佳的结果。要做到这一点，我们从两个简单的启发式：将门的数量以及和窗户享用同一墙壁的相邻房间的数量减少到最少。以及，减少建筑物角落的数量。第一个想法是基于大多数窗户时在外墙上的事实的，对于一个房间来说，一扇窗户和内门在同一面墙上是十分罕见的。第二个想法是基于大多数房间是正方形，以及每个正方形都有四个角的事实上的。有些房子有扩展，工具房以及其他的露天场所，而这些都增加了多余的角落。然而，角落的数量通常是减少支出，提高房地产效率和加热／制冷效率的。因此，楼层平面图的分数会因为多四个角加一。表V的第六排和第七排展示了alpha;minus;beta;的排除技术的应用。利用这些数值函数清除了至少几千甚至上万平面图的候选人。在第六排，当增加第一个条件时，窗户和门道的方向一起限制了内墙的方向，而在第三和第四排上，只知道门道的方向。
7.4选择最合适的拓扑结构
在探索平面图的过程中，只有得分最低的平面图们被认为是候选方案。第六排和第七排展示了刚刚谈论的这两个条件仅仅选择了探索节点的一点部分，通常，候选平面图会讲到上千个拓展方案上。在候选结构中，大多数可以因为自相矛盾而剔除掉。这些自相矛盾的平面图类似于Mobius strips 和Escher stairways :由于计算复杂性，搜索算法生成平面图，而不检查其全局一致性属性。例如多室循环或二维平面。行8到13显示了一些我们执行来消除这种类型的平面图滤波器的效果。
___房间周期:过去这样的平面图，其中两个相连的室被连接到第三室的墙壁。这种拓扑结构在二维平面是不可行的。
___房间大小:过滤去这样的房间:线性算法不可以计算这个房间的大小应为其不连续的房间相邻。
___重叠的客房:过滤掉和其他房间有重叠的房间，这种拓扑结构在二维平面上是不可能的。
___房间相邻:过滤掉这样的情况:两个房间相接，但是内壁的分配显示它们是不相接的。
___重复的平面图:过滤掉重复的平面图。这些平面图没有确切的加以说明。
___重复的形状:过滤掉这样的平面图:其中房间的大小和方位与其他房间相同，即使这两个房间相同。只有唯一一个形状能够展现给用户，并且房间的身份可以在另外一个步骤中探讨。
在这些过滤之后，剩下的平面图方案会展现给用户。用户可以从中挑选正确的平面图。注意到表IV的最后一排指明了:相较于只给出窗户位置或者运动传感器的方向，如果同时给出了窗户和运动传感器的方向会减少候选平面图的量。实际上，通过增加运动传感器的方向相较于之前的给出门道的方向减少了大致一半的候选范围。尽管窗户的方向好像是多余从表格的第四排看来，但是在解决第六排的约束冲突中是有用的。
8 评估
我们在七个不同尺寸房屋里，包括单层和多层楼的房子，布置了传感器，部署历时长达三个月。为了评估所述第一方案，光传感器部署在四个不同的房屋的窗口：A，B，C和D。在每个房屋中，我们配置了一个门道传感器（即，运动传感器和磁强计）在所有覆盖所有的内门，所有的内走廊，所有通道室内的入口的门道的顶部。我们还在每个房间的墙上部署了至少一个窗口传感器。二个房是时四个方位上都有窗户的独立住户，两个房屋是公寓或只有在两面墙上有窗户的公寓。窗口上的传感器布置以及在门道上的传感器部署的一个例子示于图3（a）中。
为了评估第四种情况的影响，在四个房屋在门道中呀布置了光传感器：A，E，F和G楼。A有光线感应器在门口和窗户上，但我们将其他三间房子布置成这样，因为在第一组实验后，房屋B，C和D都不能给我们用了。对于房屋E，F和G，我们没有布置运动传感器在门口。因此，从运动传感器数据中推断的房号和相邻性只在房屋A，B，C和D测试了，其他只能假设有100％的准确率。生活在家庭中的，包括学生，专业人士，和家庭主妇。我们分别单独评估了两家。首先，我们讨论房屋A，B，C和D，以及不同的结构限制如窗口朝向，朝向门口，或两者兼
(a)对基于不同的结构限制的方案1，2，3的比较
(b)对基于不同的光线传感器位置的方案1，2，3 的比较
而有之的他们平面图推断的效果。其次，我们讨论家园A，E，F和G和光线感应器在不同的位置___没有或在窗户上的或在门口的对平面图的影响。
8.1使用不同的结构限制
图9(b)显示了通过不同的结构限制每幢房屋(房屋A，房屋B和房屋D)产生的候选的平面图的数量;门的方向，窗户方向，或者两者兼而有之。门道方向和窗户方向的结合为三个房屋提供了最小的候选平面图范围。对于每一幢房屋，运动传感器方向对提供更小的候选平面图范围比窗户方向更有效率。然而，我们发现但在最后结果里没有显示出来的是:在房屋A和房屋B中，窗户的方向比运动传感器更有效率。总体来说，对于有更多窗户和门的房屋在窗户和门的信息中获益得更多。
由于部署大规模传感器系统的困难，对于第一组比较，我们的评估只限制于四所房屋，尽管每个房屋的平面图变化很多，我们很难得出数据性的总结。为了增加 (a)利用方案3的准确性 (b)与相邻单元相连接的准确性
图10 (a)当同时使用窗户和门道的位置信息时，从网上下载的22个拓扑结构中，绝大多数有少于10个的候选平面图。(b)在特定侧有墙但是没有窗的房子，以及随着这样的墙的数量增加随之增加的候选平面图面积。
样本的总数，我们在网上搜集了其他22所房屋的平面图。这些平面图包括了单独或者多个卧室的公寓和美国不同地区的房屋。通过分析图纸，我们人工得出房间相接，房间相对于门道的方向，窗户方向来评估我们对拓扑结构的两个条
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[148492]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
