基于智能手机的WiFi网络共享灾后运营网络架构

ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月基于智能手机的WiFi网络共享灾后运营网络架构Amitangshu PAL，天普大学MAYANK RAJ，IBMKRISHNA KANT，天普大学萨加尔·K密苏里科技大学DAS电子通信对于监测救灾行动和在灾害期间和之后向受灾民众提供援助至关重要。考虑到智能手机的普遍性，我们设想与通信基础设施失去连接（由于损坏）的智能手机仍然尽可能无缝地集成到网络中为了实现这一目标，我们建议使用WiFi网络共享技术建立断开连接的智能手机的ad hoc所提出的用于这种集成的架构和通过紧急控制中心（ECC）的定义的基于软件的控制使得能够通过智能手机传感器收集电池感知的关键数据。开发的解决方案支持所有智能手机的移动性，包括那些失去直接蜂窝连接的智能手机，以及那些没有或愿意充当网关的智能手机。我们demonstrate如何建议的计划可以绑定到标准化的无线紧急警报服务，以及它如何能够有效地处理移动容忍设备发现和数据传输。CCS概念：·网络→网络设计原则;网络协议设计;网络算法;移动网络;移动自组织网络;其他关键词和短语：灾难通信，WiFi网络共享，ad-hoc网络，基于网格的仲裁ACM参考格式：Amitangshu Jiang，Mayank Raj，Krishna Kant，and Sajal K.达斯2020年。基于智能手机的网络架构，用于使用WiFi网络共享的灾后操作ACM Trans. 互联网技术20，1，第6条（2020年2月），27页。https://doi.org/10.1145/33721456S. K. Das还是印度IIT Kharagpur的国际客座教授和SERB赞助的VAJRA教师;以及IISc Bangalore的Satish Dhawan客座教授这项研究得到了NSF资助的部分支持CNS-1461932，编号CNS-1818942，编号CCF-1725755，编号CNS-1545037，编号CNS-1545050和No.DGE-1433659。作者地址：A. K.K.（通讯作者）和K.康德，坦普尔大学，1925年。12th Street，Philadelphia，PA，19121，USA;email：{amitangshu.pal，kkant}@temple.edu; M.Raj，IBM，11550 Ash Street，Leawood，KS，66211，USA;电子邮件：mraj@us.ibm.com; S.密苏里科技大学，500 W。15th Street，Rolla，MO 65409，USA;电子邮件：sdas@ mst.edu.允许制作本作品的全部或部分数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用。版权的组成部分，这项工作所拥有的其他人比ACM必须尊重。允许用信用进行提取。复制，或重新发布，张贴在服务器上或重新分发到列表，需要事先特定的许可和/或费用。从permissions@acm.org请求权限。© 2020计算机协会。1533-5399/2020/02-ART6 $15.00https://doi.org/10.1145/3372145ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月第六章：A. J. et al.1介绍最近，持续数天甚至数周的大规模自然灾害越来越多。世界各地的例子不胜枚举，包括尼泊尔地震（2015年），波多黎各的飓风玛丽亚和休斯顿的飓风哈维（2017年），以及最近印度的飓风法尼和东南亚的毁灭性洪水（2019年）。这些灾难场景中的许多都是动态演变的，通常以意想不到的方式。因此，了解其演变情况对于在救援和疏散、保健、住所、食品、药品和其他救济行动方面提供适当的应急服务至关重要。智能手机技术的广泛使用使得智能手机越来越成为通信、人员跟踪和需求评估的生命线，特别是在灾害期间和灾害之后。考虑到智能手机携带大量传感器（例如，照相机、麦克风、运动/振动传感器、GPS等），他们收集的数据对于更好地评估受灾地区的损失和需求非常宝贵换句话说，除了典型的手动使用（如语音通话，发布文本/照片或视频到社交媒体），智能手机还可以通过（半）自动数据收集，分析和灾害期间或之后的决策提供巨大的附加价值本文旨在探讨灾难期间智能手机自动数据驱动使用中的各种问题，特别是当现有通信网络可能部分或全部损坏时。为了支持数据驱动的灾难响应服务，我们假设存在一个远程操作的应急指挥中心（ECC），它构成了数据收集、分析和决策的中心枢纽我们还假设ECC可以访问互联网，并且其操作不会受到灾难的干扰智能手机到达ECC的正常方式是通过蜂窝或WiFi连接到本地接入点。然而，它们可能会经历分散的中断，需要在智能手机之间建立自组织网络基础设施 在本文中，我们将探索一种名为E-DARWIN（使用WiFi Tether- ing的能源感知灾难响应网络）的方案，在失去（或具有非常差的）蜂窝连接的灾区建立一个ad hoc网络。 E-DARWIN利用当今大多数智能手机中可用的WiFi网络共享功能，并通过假定提前安装在所有愿意安装的智能手机上的应用程序激活。每个E-DARWIN自组织网络最终都需要连接到能够访问互联网并最终访问ECC的网关设备反过来，ECC指导数据收集，以确保最有效地使用智能手机传感器、其剩余电池电量以及该网络的延迟吞吐量特性。网关功能可以由各种设备提供。例如，救援人员携带的卫星电话或通过紧急通信车辆（ECV）空投或部署的卫星/蜂窝接入点（AP）可以充当网关。我们假设网关设备也具有WiFi能力，非网关设备可以通过该WiFi能力连接。如果灾难没有摧毁整个网络，即使是普通的智能手机也可以作为网关。更常见的情况是分散的口袋（岛屿），由于实际损坏或极端网络拥塞而没有或非常差的蜂窝连接。拟议中的特设网络将跨越这些口袋，并最终连接到外围的智能手机有手机可用性的口袋。事实上，在灾难的最初阶段，这种连通性可能是唯一可用的该网络将随着人员流动和部署更多应急资产而发展因此，进化是一个重要的组成部分， 这里讨论的机制我们专注于（半）自动化网络建设的关键原因是，携带智能手机的受影响人员可能会丧失能力、感到困惑，或者无法手动管理网络形成或数据传输虽然网络可以承载用户一种基于智能手机的灾后运营网络架构第六章：ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月生成的内容（例如，文本消息或照片），其有限的带宽和显著的延迟不适合于实时或重载内容（例如，语音或视频）。用户生成的文本和低分辨率照片可以被携带，但是需要在ECC定向和用户定向使用之间仔细分配容量，这超出了本文的范围。还可以基于嵌入式传感器自身检测到相关信号来触发网络扩建。后者的两个例子是（a）基于地震振动的地震检测[5这种增强可以很容易地纳入我们提出的计划。尽管这个概念很简单，但构建一个有用的ad hoc网络涉及许多挑战。应对这些挑战是本文的主要贡献，概述如下。(1) 确定何时以及如何构建ad hoc网络，因为仅失去连接是不够的，因此必须避免不必要的扩建以节省智能手机电池。(2) 考虑到移动性的挑战、两个设备通过WiFi网络共享连接的互补模式（客户端与热点）的要求以及找到并连接到具有网络连接性的网关设备的需要，高效地构建网络(3) 高效地调度智能手机之间的数据传输，因为ad hoc网络具有动态性、低据我们所知，我们是第一个工作，调查的建设ad hoc网络的工作，灾难的情况下，使用WiFi网络共享技术和利用提出的数据路由方案。文章的其余部分组织如下。第2节总结了相关的工作，而第3节描述的背景和建议的E-DARWIN框架的体系结构。第4节讨论了网络初始化，第5节介绍了评估其性能的分析模型。第6节介绍了基于网格法定人数的通信机制，并展示了如何将其扩展到WiFi网络共享。第7节描述了网格仲裁机制如何用于节能数据转发。第8节介绍了实验评估的E-DARWIN架构的帮助下，在Android平台上实现的原型最后，第9节结束了本文。2相关工作文献[10受灾地区的人们广泛使用的智能手机、PDA和平板电脑等无线设备的使用也提供了一种实用的方法[14，15]。即使现有的解决方案利用无线设备中的自组织操作模式来构建灾难恢复网络[16这是不可取的，因为这样的解决方案不能在所有设备上无缝支持，并且在许多国家也是非法的。这促使我们探索在无线设备上容易获得的技术的使用（例如，WiFiDirect和WiFi Tethering），用于构建灾难恢复网络。WiFi直连或WiFi对等（P2P）是一种标准，其允许设备在不需要无线接入点（AP）的情况下彼此通信[22]。WiFi Direct的工作原理是在设备中嵌入有限的无线AP，并能够“配对”两个这样的设备。尽管已经探索了用于灾害通信的基于WiFi Direct的自组织网络，在参考文献[23]中，并非所有移动平台都具有这种能力因此，为了第六章：A. J. et al.ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月在本文的第一部分中，我们选择了WiFi网络共享（或WiFi-T）作为首选技术，并指出所提出的解决方案也适用于其他技术。在参考文献[24-在确定了使用移动设备的可行性之后，作者探索了如何在机会网络环境中与其他设备通信[28]并创建计算集群网格[29]。在这样的解决方案中采用基于角色的架构，其中设备承担热点或客户端的角色以建立移动自组织网络[30，31]。相比之下，参考文献[31]中的作者提出使用网络虚拟化来让设备同时承担热点和客户端的角色。然而，在大多数当前移动设备中不支持网络接口的虚拟化。此外，参考文献[30，31]中的作者没有解决与网络形成，路由和维护相关的问题。基于与充当接入点的客户机的偶然相遇的主动网络（例如，具有特殊紧急AP的警察巡逻车）在文献中已经被考虑[32然而，我们的目标是建立不是短暂的网络，因为它们更有可能是有用的持续监测。最后，我们注意到，这项工作的一个初步版本与不同的数据转发方案发表在一次会议上[35]。相比之下，本期刊版本中考虑的数据转发方案基于网格仲裁技术，旨在处理智能手机的移动性。此外，我们已经提出了详细的网络初始化过程，通过exploiting无线紧急警报（WEA）服务广泛部署在美国和几乎所有的智能手机上。虽然会议版本提出了一种博弈论机制来利用数据冗余，从而可以减少数据传输（因此电池消耗），但期刊版本并不关注数据冗余方面。3背景和问题描述3.1网络概述和主要假设如上所述，假设每个智能手机都配备有E-DARWIN应用程序，其可以帮助建立自组织网络以在智能手机中的可用传感器的程序控制下收集数据（例如，照相机、麦克风、陀螺仪、GPS等），并将数据传送到网络的下一级。后者由网关设备组成，包括具有幸存/建立的蜂窝链路和紧急AP的智能手机。我们假设，一些幸存的基站和“车轮上的细胞”（COW）是在其有限的覆盖范围内运作。COW是安装在拖车或卡车上的移动、便携式蜂窝塔和收发器，便于在受影响地区部署[36]。紧急WiFi AP与受影响地区的卫星网关一起部署[37]。每个卫星网关由一个甚小口径终端（VSAT）碟形天线和一个卫星调制解调器组成，可以很容易地组装和拆卸便携式[38]。当道路连接可用时，在紧急车辆的帮助下，在受影响区域的各个位置部署具有卫星网关的WiFi AP如果在受影响区域内没有可用的道路连通性，则设备可以由应急人员携带或空投，如参考文献[38]中所建议的，并以类似方式部署。由于AP专用于协助应急网络，我们假设 它们通过ECC进行预认证，并使用传统技术（如卫星网络）连接到ECC [37]。此外，假设所有智能手机都能够通过众所周知的URL到达ECC。ECC是由公共援助机构（如美国的联邦紧急事务管理局（FEMA））在一些安全的地方建立的，用于提供灾难救援;它是一个永久性的实体，只需要在必要时启动我们一种基于智能手机的灾后运营网络架构第六章：ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月Fig. 1. E-DARWIN的网络架构进一步假设ECC具有必要的权限，可以信任，并且在灾难事件后不久就上线。ECC形成整个应急网络的顶点，确定数据收集需求，收集和分析所有数据，指导网络重构等。E-DARWIN架构如图1所示。尽管在下一级网络上有许多重要的问题需要解决（例如，应急通信车辆或ECV的定位、通信技术的选择等），我们在这篇文章中的重点主要是灾难网络的智能手机端。3.2灾难环境下可能的无线技术尽管存在许多可以支持智能手机之间的P2P通信的技术（当前可用或正在开发中），但是它们中的大多数都受到一些限制。例如，长期演进（LTE）-占主导地位的4G技术-也正在扩展用于具有新兴LTE直连标准的P2P通信[39]。然而，LTE直连确实需要用于设备发现和连接建立的中介（小区塔），这在灾难场景中是有问题的。然而，随着微蜂窝/微微蜂窝塔的部署，LTE和LTE直连在灾难中非常有用。部署这些服务可能需要数小时甚至数天的时间，但这不是本文的重点。类似地，尽管ad hoc模式WiFi是一种相当古老的技术，但它仍然没有得到广泛支持，并且通常需要设备上的root访问来设置[28]。另外两种有前途的技术是WiFi Direct和WiFiTethering。实际上，WiFi直连或WiFi P2P是一种较新的标准，其通过在设备中嵌入有限的无线AP来允许设备到设备通信。使用WiFi Direct，一些设备可以形成一个组，其中一个设备作为组所有者，而其他设备作为组成员。 根据WiFi联盟[40]，“WiFiDirect认证的网络可以是一对一或一对多的。连接到多个其他设备是一项可选功能，并非所有WiFi Direct认证的设备都支持该功能;某些设备只能进行1：1连接。” Thus, WiFi direct devices that support only1:1 connection are not quite suitable for a为此，WiFi网络共享（简而言之，WiFi-T）作为允许与其他附近设备共享移动终端的互联网连接WiFi-T得到所有主要设备制造商的普遍支持，并可在所有主要移动操作系统平台上使用，例如iOS 4.3+，Android 2.2+和Windows 7.5+。WiFi-T还允许设备充当WiFi热点，而在其通信范围内的其他设备可以连接到它。WiFi-T的使用要求设备在客户端和热点模式之间交替以转发数据（因为链路可以第六章：A. J. et al.ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月图2. E-DARWIN框架的两个阶段仅存在于客户端和热点之间）。这基本上导致了延迟容忍网络（DTN），其中大多数链路根据需要选择性地和间歇性地建立，这从最小化智能手机电池消耗的角度来看也是至关重要的。关键的挑战包括相互设备发现或初始化，在其顶点构建具有ECC的整个网络，有效地收集数据，并通过考虑智能手机的电池消耗、可用带宽、可达性、数据传输延迟要求以及所收集数据中的冗余利用来将它们递送到ECC请注意，几乎所有当前的智能手机都支持（在基础设施模式下）WiFi标准; WiFi-T功能也可用于几乎所有现有的智能手机;并且WiFi热点可以连接到多个客户端。因此，我们专注于WiFi-T作为关键的通信技术，在灾难发生后建立ad hoc网络。虽然WiFi Direct也越来越受欢迎，但其渗透率仍远低于WiFi-T。虽然可以将WiFi直接集成到E-DARWIN中，但这超出了本文的范围。3.3基于WiFi Tethering的网络如图2所示，所提出的E-DARWIN框架中的智能手机网络在两个阶段中运行--转发阶段和数据转发阶段。我们假设所有设备都安装并启用了E-DARWIN应用。当通过紧急事件触发时，每个设备上的应用程序都会进入紧急阶段，以发现邻居并构建自组织网络;最终，它要么确认紧急事件并进入数据转发阶段，要么简单地折叠，即，没有真正的紧急情况。在数据转发阶段，每个设备根据其可用电池容量和数据传输需求调整其占空比和传输时间表，并定期转发采样数据。第4节和第7节详细介绍了这两个阶段。基于WiFi-T的操作要求每个设备处于以下三种状态之一：休眠：默认情况下，设备处于休眠状态以节省能源，直到它被安排作为WiFi热点或客户端。休眠状态将禁用设备的所有网络接口，设备在CPU休眠的低功耗模式下运行。此状态不同于媒体访问控制（MAC）层中的休眠状态，在媒体访问控制（MAC）层中，存在活动数据连接，并且仅无线接口被周期性地关闭以节省能量。WiFi热点：在此状态下，设备重复广播网络发现信标，以便任何相邻客户端都可以与之关联并交换数据包。在进入休眠或客户端状态之前，设备在预定的时间间隔内充当一种基于智能手机的灾后运营网络架构第六章：ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月联系我们图3. E-DARWIN的功能WiFi客户端：在此状态下，设备定期扫描无线信道以查找来自热点的广告并与之关联在成功关联时，连接到热点的客户端设备参与数据转发或接收。只要存在与其热点邻居中的任何一个的一些数据传输，设备就保持在客户端状态，并且相应地进入休眠或热点状态。设备可以在处于热点或客户端状态时捕获数据。如果设备被安排在休眠状态下捕获数据，那么它将唤醒并再次休眠3.4说明性示例图3显示了初始化阶段之后E-DARWIN中设备的典型行为设Dm代表设备m一，二，...，8 .假设在t=25分钟时，D3被调度为WiFi热点，而处于D3的通信范围内的D1、D2和D4作为WiFi客户端醒来并与之关联，则在t=25分钟时，D1和D2可以将其存储的数据包转发给D3，D3在接收到这些数据包时可以将其转发给D4假设设备被配置为充当WiFi热点或客户端达2分钟，则设备在变为休眠之前保持在它们各自的状态中直到t=27分钟。在t=27分钟时，D5和D6被调度为分别在热点和客户端模式下唤醒。D4进入客户端模式并与D5关联.因此，D6将其分组发送到D5，D5在同一时隙中转发到D4然而，由于D4已经存储了要转发的分组并且它在WiFi AP的范围内，所以它在t=29分钟处切换到客户端模式并且关联到AP以转发其分组。D4还在同一时隙中将其他设备发送的数据包转发给AP。类似地，在t=34分钟时，D8进入热点模式，而D7被调度为在客户端模式中唤醒。因此，D7在t=33分钟时与D8关联以转发其分组，然后D8在t=36分钟时的下一时隙中将其分组转发到WiFi AP。以这种方式，设备自主地形成多跳树拓扑以将它们感测到的分组转发到AP。第六章：A. J. et al.ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月图第四章综合公共警报和警告系统。图片来自FEMA [41]。4初始化阶段4.1激活E-DARWIN应用程序E-DARWIN网络的初始化旨在解决两个相互依赖的问题：（a）基于WiFi网络共享，发现邻居以建立本地连接的智能手机集群，这些智能手机可以通过网关设备连接到互联网;以及（b）以最小的能量消耗，确保网络可以服务于紧急（灾难）场景。为此，特别是在美国。在这种情况下，我们将E-DARWIN连接到官方紧急警报系统，例如无线紧急警报（WEA）系统。图4描述了美国当前使用通用警报协议（CAP）通过开源集成公共警报和警告系统（IPAWS）广播来自官方来源的警报的系统，其目标是集成各种子系统，包括涉及无线蜂窝运营商的WEA [42]。（类似的系统可能在世界其他地方也存在。目前，美国的大多数蜂窝服务提供商都在所有Android/IOS手机中支持WEA。注意，WEA消息在控制信道上运行，因此不受网络拥塞的影响。我们假设WEA警报，例如对安全的迫在眉睫的威胁（例如，海啸、龙卷风、飓风、台风警报）触发E-DARWIN应用程序。这是一个合理的假设，因为WEA警报会广播到受影响的地区;在收到WEA警报消息后，手机会解析和分析以确定它是否易受攻击。为了简单起见，我们假设非易受攻击的手机没有任何角色可供使用，除非应用程序被手动启动并指示参与。这一假设的意义在于，我们不希望非易受攻击的手机参与网络（除非用户故意选择手动启动应用程序4.2启动网络构建即使在E-DARWIN应用程序确定手机易受攻击后，它可能也不会开始构建基于WiFi的网络，直到它实际上失去了蜂窝连接。换句话说，具有蜂窝连接的电话将不会加入并充当网关。因此，对于实际失去蜂窝连接的受影响的易受攻击设备（AVD）和不失去蜂窝连接的未受影响的易受攻击设备这些设备可以使用它们的国际移动设备标识（IMEI）或其他唯一信息作为发现过程中的ID;可以合理地假设每个设备都保持相当准确的时间（低至几秒）。一个易受攻击的设备在一段固定时间（比如15分钟）内连续失去蜂窝连接，将自己归类为AVD并启动发现过程。如果它稍后在一段固定时间内重新获得蜂窝连接，那么它可以将自己重新分类为UVD。我们通常认为从AVD到UVD的转变是非常罕见的，因此后面将讨论UVD的一个完全独立的机制。识别灾难并从正常模式切换到易受攻击模式的过程如图5所示。一种基于智能手机的灾后运营网络架构第六章：ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月图5. E-DARWIN应用程序初始化、发现灾难以及从正常模式切换到易受攻击模式的流程图随着AVD之间的发现的进行以及WiFi网络共享的扩展，详细说明过程最终包括具有蜂窝接入的电话和部署在灾区的紧急AP实际上，在蜂窝网络的丢失或降级之后，紧急AP的部署可能花费一些时间因此，可能需要拆除无法到达ECC的已经构建的节点集群。然而，当新的紧急AP最终被部署或蜂窝接入至少部分地起作用时，应该可以重试。由于大多数灾害的影响是渐进的，因此一个区域中最初可能有足够的UVD，使得每个AVD集群可以使用其中一个或多个UVD作为网关。稍后，随着蜂窝连接性的降低，一些AVD集群可能会在一段时间内完全隔离，并且稍后在它们变得在线时再次通过AP到达ECC在任何情况下，全面覆盖通常是有关发现过程的详细信息，请参见第4.3节。UVD作为网关的选择由ECC控制，ECC根据给定区域中UVD的密度、区域中AP的数量、流量需求等来招募UVD。但是，这种招募过程的详细信息不在本文的范围内。4.3邻居发现当E-DARWIN应用程序被激活时，设备需要发现它们的邻居，包括它们的时间表。如上所述，在灾难期间需要考虑两种类型的电话：AVD和UVD。（我们假设AVD无法访问互联网，即使它在中断之前连接到正常的让我们首先描述AVD如何发现彼此。我们假设时间被划分为持续时间为Δ的“时隙”。文献中用于邻居发现的现有解决方案依赖于设备之间的协调，以确保它们的无线电同时打开，以便发现彼此[43，44]。使用WiFi网络共享，它们必须打开WiFi无线电并保持在不同的状态（例如，一个充当WiFi热点，另一个充当WiFi客户端）。为了解决这个问题，在初始化阶段，设备被限制为停留在热点状态对于T初始化插槽。在该阶段期间，设备在从接下来的[1，C盘]时隙中均匀随机选择的下一个C下一个时隙中连续地承担WiFi客户端的角色。这允许设备在随机时隙之后处于不同的状态，从而发现彼此。在初始化阶段，处于热点状态的设备等待它的一个邻居成为客户端并与其关联。当设备成为客户端时，它将在该状态下停留一个时隙。客户端设备扫描无线信道以寻找来自其可能处于热点状态的邻居之一的广告。在从热点接收到广告时，客户端设备与其相关联在成功关联时，设备将彼此添加到邻居列表并交换彼此UVD还需要参与发现过程，以便它们可以连接到AVD，但是期望它们不断尝试发现它们的邻居是不合理从E-DARWIN的角度来看，UVD将在客户端模式下短时间打开其WiFi无线电，以便它可以在热点模式下发现附近的任何AVD。唤醒频率可以是周期性的，第六章：A. J. et al.ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月我]图第六章在路由阶段发现相邻设备的流程图适应性在自适应唤醒机制中，UVD以小的睡眠持续时间（例如，15分钟）开始，并且只要没有发现新的AVD，则UVD在下一轮以指数方式增加直到最大阈值(say，1小时）。如果发现任何新的AVD，则睡眠持续时间 降低到初始值。这样的发现机制确保如果在UVD集群的邻域中没有AVD，则它们将不会形成任何网络，因为它们全部将处于客户端模式。与此同时，任何AVD都将被联系，因此将能够使用UVD作为网关。每个设备还跟踪它最近与谁通话（几个小时），以避免重复的连接建立和认证消息交换。发现过程如图6所示。如果UVD通过连接到WiFi接入点（AP）来接入互联网，则发现机制对UVD有影响。在这种情况下，将要求UVD周期性地断开其与正常AP的关联，使得其可以连接到AVD。这破坏了UVD的用户体验，除非蜂窝连接可以透明地替代WiFi，而UVD用作到AVD的网关。大多数智能手机可以在蜂窝和WiFi接入之间来回切换，而无需用户干预。此外，这种转换需要更好地协调，因为它是由有计划的行动而不是弱信号触发的。最后，当UVD切换回连接到WiFi AP时，它应该与其正常AP而不是碰巧处于热点模式的AVD之一相关联。5发现性能分析模型本节介绍一个分析模型，研究算法参数对AVD发现其邻居的概率的影响表1列出了必要的参数。如第4.3节所述，我们将时间划分为离散的5.1AVD发现设A和B表示处于初始化阶段的两个设备每个设备从下一个C盘时隙中选择下一个随机时隙C假定每个设备在初始化阶段保持T个初始化时隙，则它们将在至少ρ=T个初始化/C个盘时间成为客户端。为了简单起见，我们假设Tinit是Cdisc的倍数，使得ρ是整数。现在，如果A和B不在同一时间段内成为客户端，它们将发现彼此。因此，P（A和B会发现彼此）=1 −1/（C圆盘）ρ。（一）一种基于智能手机的灾后运营网络架构第六章：ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月N. −Σ我我{}表1.符号表及其意义Δ发现阶段T初始化初始化阶段C盘在初始化阶段C下一个随机时隙∈[1，Cdisc]，之后AVD在初始化期间进入客户端模式ρ初始化阶段我UVD的最大睡眠持续时间、S时隙数中UVD的最大休眠持续时间，即，s=IΔNAVD的UVD邻居数（Ra，Ca）设备a图第七章（a）具有不同C盘和ρ的两个AVD之间的发现概率。在UVD和ADVB之间的发现概率，（b）变化的C盘和（c）变化的T初始。图7（a）显示了两个AVD发现彼此具有不同的C盘和ρ的概率。我们可以观察到，随着C盘的增加，两个设备可以选择相同的时隙成为客户端的概率我们还可以观察到，设备发现的概率随着ρ的增加而增加。从图7（a）中，我们注意到AVD需要成为客户端至少4次才能以>99%的速度发现彼此。如果Tinit≥4 ×C圆盘，则确保该概率。5.2UVD和AVD我们现在推导出在初始化阶段，AVD被至少一个UVD邻居发现的概率。我们考虑UVD的睡眠间隔是时间单位的最坏情况场景，其相当于s=fΔ时隙。让我们考虑两个邻居A和B，分别代表UVD和AVD。在最初的-在客户端模式转换阶段，AVD在任何时隙中保持在热点模式，并且偶尔以1/C盘的概率进入客户端模式。因此，在初始化阶段期间的任何时隙处，AVDB以概率Ph=1 1/C盘保持在热点模式中。A在B的初始化阶段内醒来的概率如图8所示。作为-在时间实例0处，B开始其初始化阶段，其中T_init=5个时隙。在最坏的情况下，UVDA在每s个时隙中唤醒一次，在图8中假设为8。请注意，在任何时刻，UVD都停留在s个状态中的任何一个，s个状态定义为A将在其之后唤醒的时隙数。例如，在图8中，我们假设s=8。也就是说，在时刻0，如果A处于状态S0，则它在时隙0唤醒;而如果它处于状态S7，则它在7个时隙之后唤醒因此，在时刻0，UVDA以1/s的概率停留在s个状态中的任何一个。然后，如果A在时刻0停留在状态S0、 S1、 S2、 S3、 S4中的任何一个，则A在B的初始化阶段内醒来换句话说，A在T个初始化时隙中的任何一个时隙中醒来的概率为min。1，Tinit/s因此，第六章：A. J. et al.ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月1否则。N1否则。我≥ ×≥N ≥图8.举个例子。UVD发现其相邻AVD的概率由下式给出：P（客户端和热点模式下的A和B）=。PhTinit/s如果PhTinit95%。再加上=1小时，UVD只需要在其时间的0.833%内保持其WiFi无线电开启，这确保了该方案在发现阶段不会给UVD带来重大负担。6 Quorum基于网格的通信在T个初始化时隙之后，AVD移动到数据转发阶段。UVD在发现它们的第一个AVD之后也移动到该阶段T初始化时隙。在数据转发阶段（也称为自适应阶段），设备大多保持休眠状态以节省电池电量，偶尔会进入热点（或客户端）模式进行必要的通信。对于该阶段，我们采用如下所述的用于设备的基于定额的占空比方案。假设时间被划分为时隙，每个时隙足够大以容纳多个传输，我们现在将法定数量集定义如下：定义6.1（法定人数集）。 仲裁集表示设备唤醒时的时隙。在非法定时隙中，允许设备进入睡眠模式以节省能量。法定数量集的概念最初是在能量感知的ad-hoc网络[45]和低功耗传感器网络[46，47]的背景下提出的为了确保设备可以彼此通信，选择法定集合，使得任何两个设备将在某些时隙唤醒并彼此连接换句话说，在各个设备的仲裁集之间总是存在非空交集一种基于智能手机的灾后运营网络架构第六章：ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月××图9.基于网格的法定人数。定义6.2（基于网格的法定人数）。在基于网格的仲裁中，每个连续的n2个时隙被认为是一个仲裁集，它们被安排在一个nn网格。网格中的方形框表示时隙。每个设备独立地从n n网格中选择一行和一列作为仲裁集。基于网格的仲裁的概念如图9所示，其中设备A选择行Ra和列Ca作为其仲裁，而设备B选择行Rb和列Cb。该图还显示了设备A和B的法定集合之间存在两个交叉点-一个用于Ra和Cb，另一个用于Ca和Rb。如上所述，设备必须在所选法定人数处唤醒，这意味着这两个设备都将在这些交叉点唤醒并进行通信。然而，这种基于法定人数的网格分配不能直接应用于基于WiFi网络共享的通信，这是由于设备需要以不同模式唤醒的附加要求。这就产生了需要开发一个新的基于网格的仲裁集生成方案。目的是确保设备可以发现其相邻设备，而不管移动性如何，只要在有限的时间量内任何设备之间存在有效的重叠。定义6.3（有效重叠）。当 两个设备中的一个处于热点模式而另一个处于客户端模式时，时隙中的有效重叠发生在两个设备之间。为了确保设备共享一些有效的重叠插槽，我们需要强制执行法定网格公式的三我们的问题在以下意义上不同于传感器网络中的邻居发现方案[45与重叠确保成功发现的相关工作不同，我们的方案需要确保两个设备之间的有效重叠意味着成功发现。下面，我们描述了成功的基于WiFi网络共享的通信的三个网格分配原则。(A) 第一条规则：网格的每一行由n个连续的（modn2）槽组成。例如，在图10中，行由n=4个连续时隙组成，即，（1. . 4），（5.. . 8），（9.. . 12），（13.. . 16）。(B) 第二个规则：m ∈ [1，2，...，n2]，任意n个连续槽[m，m +1，. ，m + n − 1]（mod n2）（4）分布在n个不同的列中。例如，在图10中，在m= 2的情况下，槽（2.. . 5）被分配到n列。使用这两个简单的网格形成原理，任何相邻设备都有一些相交的槽，这在参考文献[45]中得到了证明。(C) 第三条规则：对于基于WiFi网络共享的通信，两个设备必须同时在不同的模式（即，热点和客户端）。为此，每个设备都有两个不相交的法定集合：一个用于热点模式，另一个用于客户端模式。两个不相交的仲裁集可以很容易地从n×n网格中提取出来，第六章：A. J. et al.ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月×××图10. 设备A和B的热点和客户端插槽相交的示例。图十一岁设备A和B在一个周期内不重叠的示例和列是不同的。热点和客户端模式共有两个插槽，我们称之为公共插槽（CS）。在这种情况下，代表行的状态将获胜。在定理6.5例如，在图10中，设备A选择（行2，列2）和（行4，列4）作为热点和客户端序列，导致两个公共槽8和14分别被选择作为热点和客户端。定义6.4（周期）。一 个n n网格的周期是n2，对于图10中的4 4网格是16。因此，在16个时隙之后，设备A重复相同的序列。6.1无有效法定人数的概率使用上述网格形成原理，两个设备通常在有限的时间量内找到有效的重叠。例如，在图10中，节点A和B在热点模式和客户端模式中在时隙2、5、12和15中相交（反之亦然）然而，存在两个设备没有找到有效重叠的特殊情况如果满足以下三个条件，就会出现这种情况：(a)两个设备A和B具有相同的网格尺寸;（b）它们为它们的热点和客户端状态选择完全相同的行;以及（c）A在这样的场景中，设备的客户端插槽永远不会与另一设备的热点插槽重叠，反之亦然。这种情况如图11所示，其中A和B的网格尺寸都4 4，满足上述条件（a）此外，设备A选择（行2，列2）和（行4，列4）作为热点和客户端序列，而B分别选择（行2，列1）和（行4，列3）作为热点和客户端序列，因此条件（b）和（c）也被满足。然而，这种现状集合生成不会在A和B之间生成有效的重叠。下面，我们证明这种特殊情况发生的概率非常低。一种基于智能手机的灾后运营网络架构第六章：ACM Transactions on Internet Technology，Vol.号201.第六条。出版日期：2020年2月n−n2（n−1PPP×图12岁不与n重叠的概率。第6.5章. 在均匀（或相同）网格尺寸n×n中，两个设备不会经历具有概率P=P1P2的有效重叠，其中P1=n（11）P2=n2−3n+3。P屋顶。 证据见附录A.1。□我们现在声称，即使对于小的n，它也