公开/公告号CN112868255A
专利类型发明专利
公开/公告日2021-05-28
原文格式PDF
申请/专利号CN201880088519.6
发明设计人 阿布德雷扎克·拉希迪;哈基姆·巴迪斯;
申请日2018-12-04
分类号H04W40/22(20060101);H04W84/18(20060101);
代理机构11332 北京品源专利代理有限公司;
代理人谭营营;胡彬
地址 法国马恩
入库时间 2023-06-19 11:06:50
技术领域
本发明涉及一种允许最终用户终端通过具有动态架构的无线多跳通信邻近网络进行交换的方法和组件,所述动态架构的节点是静态用户终端或低相对移动性的终端。
方法和组件有利地适用于根据协作服务的交换,例如但不限于,道路部门(导航辅助,交通信息等)。
背景技术
传统上,例如,通过示例但非限制性的协作的实例,将实时类型的应用托管在远程资源(“云”(以下使用的英语术语)-专用或公共)中。这提供了对外部计算资源(存储容量,处理能力等)的流畅且无缝的接入。
这些实时类型的应用要求有限的响应时间,以避免实时接收和显示数据(位置,速度等)时出现延迟。这个响应时间包括两个部分:用于云接收和处理信息的时间,以及数据穿越用户和云之间的网络的时间,以及数据返回穿越的时间。
尽管存在可以在云中优化处理时间的手段,但返回时间本身仍然不可控,这是因为返回时间取决于几个参数:云与最终用户之间的距离、传输网络中数据拥塞的风险、用户连接到的无线电接入网络的覆盖范围和质量访问网络,其中与无线电接入网络是蜂窝(3G/3G+/4G/5G)还是WiFi(IEEE 802.11n/ac/p)无关。
本发明提出了一种方法和通信系统,所述方法和通信系统作为减少用于访问协作服务的返回时间的策略的一部分,并且作为用于降低网络架构的成本的策略的一部分。
同样显而易见的是,当前的解决方案要求用户具有对云服务的访问并且具有因特网连接的能力,尤其是通过WiFi、3G/4G/5G网络等。但是,这种连接可能是不可用的,尤其是如果用户位于无线电覆盖区域之外或没有新的可用性的区域中,例如当附近的接入终端达到其最大连接数量时。
同样地,由于干扰所引起的质量差的无线电链路,或者甚至当蜂窝通信分组用尽时,也可能使用户无法访问所述服务。
此外,与在获利的接入网络上传输的数据使用相关的成本也可能是障碍。
发明内容
本发明的目的是使最终用户接近信息并且除了远程资源(“云计算”)之外还利用本地资源(根据下文使用的英语术语“雾”)以减少返回时间并吸收接收数据时的延迟。
本发明的另一个目的是允许客户端通过尽可能少地请求传统接入网(3G/3G+/4G/5G)来与所提供的应用程序或现有应用程序进行交互。
本发明的又一个目的是依靠用户的协作和参与社区(驾驶员、行人、骑自行车的人、商人、当地社区……)来丰富数据库、优化计算并对社会特性进行响应。
特别地,根据一个方面,本发明提出了一种用于在终端之间进行通信的方法,当这些终端处于允许无线邻近通信的距离时,所述终端适于在终端之间执行无线邻近通信,以及与远程资源进行单独通信。
在这个过程中,使用静态或低相对移动性的终端,以便它们共同形成具有动态体系结构的本地通信网络的节点。位于一定距离并与静态用户终端或低相对移动性的终端中的至少一个建立无线邻近通信的不同终端,可以在这个网络上彼此进行交换。
这样,本发明更具体地提出了一种在最终用户终端和静态用户终端或低相对移动性的终端之间相对于彼此进行通信的方法,当这些终端处于允许无线邻近通信的距离时,这些终端适于通过作为无线通信链路的第一通信链路在终端之间进行无线邻近通信,以及通过作为蜂窝通信链路的第二通信链路分别与至少一个远程资源服务器进行通信,其中远程资源服务器是通过“云计算”类型的网络可访问的控制服务器;
在所述方法中:
-静态用户终端或低相对移动性的终端共同形成具有动态架构的多跳邻近通信网络的节点,并在其间在所述网络中通过其第一无线通信链路进行交换,
-多跳邻近网络的这些静态用户终端或低相对移动性的终端至少与控制所述多跳邻近网络的架构的控制服务器进行交换,
-以及其它用户终端是最终用户终端,并且通过第一无线通信链路与网络的静态用户终端或低相对移动性的终端中的至少一个进行通信,
所述方法包括以下步骤:
每个终端通过第二蜂窝通信链路向控制服务器传送控制信息,控制信息例如是识别和定位的信息,以及与至少一个技术参数有关的信息,
-根据接收到的控制信息,所述控制服务器:
从所有终端中选择静态终端或低相对移动性的终端,将其它终端称为最终终端,
确定图,所述图的节点是静态终端或低相对移动性的终端,如果两个节点之间的距离小于允许两个节点通过动态多跳邻近网络在它们之间直接交换的距离,则通过网桥将两个节点连接,
在这个节点图上确定支配节点的子图,对所述子图的确定进行优化,以使节点数量减至最低并遵守对至少一个给定技术参数的给定约束,
在支配节点的子图中,选择至少一个网关节点,所述网关节点适于通过节点的第二蜂窝通信链路与云计算类型的网络建立通信,
将图中不属于子图节点的节点选择作为仅具有用于最终用户终端的与动态多跳邻近网络进行接入/中继功能的节点,
仅通过第二蜂窝通信链路分别向每个不同的静态终端或低相对移动性的终端传送其分层状态:网关节点、支配节点或归属于它们的简单接入/中继节点,以根据静态终端或低相对移动性的终端的持续配置,在一段时间内构成动态多跳邻近通信网络。
有利地,一旦所述动态多跳邻近通信网络完成,当最终用户终端或静态用户终端或低相对移动性的终端发出请求时,所述终端:
在第一种情况下,通过支配节点到多跳邻近通信网络的第一条无线通信链路发出,支配节点适于管理所述请求以响应询问所述节点的终端,
在第二种情况下,在支配节点没有令人满意的响应的情况下,向控制服务器发出,直接通过其第二蜂窝通信链路或通过作为网关节点的另一终端,经由这个其它终端的第二蜂窝通信链路与控制服务器进行通信。
所述控制服务器可以将所述图细分为多个感兴趣的地理区域,为感兴趣的地理区域定义一个或多个技术参数,并且计算在这些感兴趣的地理区域中具有静态终端或低相对移动性的终端的动态多跳邻近通信网络。
控制服务器可以对几个技术参数执行其处理,并且定义这些技术参数的优先级顺序。特别地,控制服务器可以在每个感兴趣的地理区域中定义优先级顺序。
可以从以下列表中选择经由终端被传送到控制服务器的一个或多个技术参数:
–与其它终端的连接程度(直接相邻节点的数量);
–无线电覆盖范围(无线电范围);
–连接质量;(1)终端与运营商网络之间的连接质量,以及2)终端与邻近网络之间的连接质量);
–用于数据存储的存储容量;
–可用的电池电量等级;
–终端的速度(终端相对于地面的速度(“常规”速度)和相对于相邻终端的相对速度);
–终端到动态多跳邻近网络的连接质量;
–社交网络特性终端的所有者的电子声誉或其它信息。
同样,可以通过以下内容来定义所述技术约束:
–阈值,尤其是当技术参数是无线电覆盖范围时;或者
–用于技术参数的2到4个间隔类别,尤其是当技术参数是用于数据存储的存储容量或可用电池电量等级时。
特别地,可以为感兴趣区域中的无线电覆盖范围的阈值定义所述技术约束。特别是:,
–使用两个技术参数:连接程度和无线电覆盖范围,无线电覆盖范围的优先级顺序低于连接程度的优先顺序;
–计算节点的无线电覆盖范围与一个或多个感兴趣的地理区域的重叠,将在一个或多个感兴趣的地理区域中具有最大无线电覆盖范围的节点保留作为支配节点,以及对要在确定的支配节点的无线电覆盖范围之外覆盖的感兴趣区域ZI的表面进行重新初始化,以在必要时找到其它附加的支配节点来覆盖感兴趣区域ZI;感兴趣的地理区域(ZI)是由应用程序定义的区域,并且可以采用具有固定或不同尺寸(可以根据无线电范围来标识尺寸)的多种形式(圆形、正方形、多边形等))。
数据可以被托管在所述动态多跳邻近通信网络的支配节点中,并且数据源自云计算类型的网络、所述控制服务器和/或终端,所述支配节点能够在其间通信和共享数据。
第一无线通信链路的外部通信范围小于300米,并且并且所述第二蜂窝通信链路的外部通信范围超过400米。
例如,终端被配置有用于其第一无线链路的WiFi和/或蓝牙和/或Zigbee和/或V2X和/或C-V2X、DSRC通信接口,以及用于其第二蜂窝通信链路的2G和/或3G和/或4G和/或LTE和/或5G通信接口,控制服务器符合SDN模型,每个终端具有相应的控制单元。
当控制服务器检测到静态终端或相对移动性较低的终端的到达和/或离开时,它可以重新开始确定由静态终端或相对移动性较低的终端构成的网络节点的状态。
为了确定包括一个或多个感兴趣的地理区域的子图,所述控制服务器执行可以四个连续的步骤:
–在第一步骤中,在所述图中形成最大独立集(MIS),并且如果所述图包括一个或多个感兴趣的地理区域,则独立地在所述子图的一个或多个感兴趣的地理区域中形成最大独立集(MIS);
–在第二步骤中,通过以下方式形成最小支配集(mDS):
–(i)计算所述图的每个节点的一个或多个技术参数的分数,以获得第一支配节点,
这些分数满足对支配节点的一个或多个技术参数的约束,(分数是给定度量标准中技术参数的值。特别是,在多个技术参数的情况下,这个度量标准是混合度量标准,值(也被称为分数)是不同技术参数的值的函数;为了这个目的,这些值必须进行转换以显示在同一字段中(例如,在区间[0-1]中)。此外,这些技术参数不需要具有相同的重要/优先程度。因此,每个技术参数都有权重系数,权重系数表示重要性或相对于其它技术参数的差异);一旦固定了这些黑色节点,它们的分数就不再重要,并且然后通过计算后者的分数来确定其它黑色节点。
–(ii)更新一个或多个技术参数的分数,
–(iii)通过重新开始阶段(i)和阶段(ii),直到剩余节点不满足约束为止,确定除第一支配节点之外的其它第二支配节点;
–在第三步骤中,将剩余的节点更新为已合并所有感兴趣区域的整个图上的支配节点;以及更新所述一个或多个技术参数的分数,并通过所述支配节点确定其它支配节点;
–在第四步骤中,将支配节点彼此互连以形成最小连通支配集(mCDS)。
在第一步骤中,针对给定技术参数的给定技术约束,所述控制服务器可以预先消除不遵守期望间隔类别的节点,其中通过计算技术参数的分数来确定间隔类别。特别是,在组合所有感兴趣区域以形成整个图之后,所述控制服务器在第三阶段中将受支配的节点转换为支配节点。
在可能执行的方法中,特别建议:
–相对于至少一个第二技术参数,第一技术参数可以具有优先级;
以及:
–在第二步骤中,支配节点的状态归属于其分数符合第一个技术参数的优选区间类别(或给定阈值)的节点,
以及在与一个或多个节点相等的情况下,其分数符合优选区间类别(或阈值),
符合第二类技术参数的优选区间类别(或具有更高分数)的节点,
以及在与一个或多个节点的新相等的情况下,其分数符合第二技术参数的优选区间类别,
还符合第三技术参数的优选区间类别的节点,第三技术参数的优先级将低于第二技术参数的优先级,或者如果没有第三技术参数,则是这些节点中的一个节点,
-并且然后,在第二步骤中,将中间节点的状态归属于作为合格的主导节点的节点的并且并且不是主导节点的相邻节点。
方法尤其适用于以下情况:终端是集成了可以是嵌入式或非嵌入式的通信系统的设备、便携式电话、计算机的车辆。
低相对移动性的终端例如可以意味着,终端之间的速度小于或等于行人速度的终端/保持在感兴趣区域中/并且始终通过动态多跳邻近网络保持与雾的相同的静态终端或相邻的低相对移动性的终端进行连接的终端,例如固定车辆。
本发明还涉及一种包括最终用户终端和静态用户终端或低相对移动性的终端的组件,当这些终端处于允许无线邻近通信的距离时,适于单独通过第一无线通信链路在终端之间进行无线邻近通信,以及通过第二蜂窝通信链路分别与远程资源进行通信,
在静态用户终端或较低低相对移动性的终端中,共同形成具有动态架构的多跳邻近通信网络的节点,
被称为最终用户终端的其它终端通过第一无线通信链路与网络中的静态用户终端或低相对移动性的终端中的至少一个进行通信,
所述组件还包括所述网络的架构的至少一个远程控制服务器,所述远程控制服务器自身连接到云计算类型的网络,并且多跳邻近网络的静态用户终端或低相对移动性的终端与至少一个远程控制服务器进行交换,
最终用户终端仅通过第二蜂窝通信链路将其控制信息传送给控制服务器,并且仅通过其第一无线通信链路与动态多跳邻近通信网络进行通信,
静态用户终端或低相对移动性的终端的功能如下:
–被称为支配节点的静态终端或低相对移动性的终端对最终用户终端的请求进行响应并托管来自云计算类型的网络、控制服务器和/或终端的数据,这些静态终端或低相对移动性的终端中只有一些是支配网关节点,支配网关节点通过第一无线通信链路和/或第二蜂窝通信链路与控制服务器进行通信;
–静态终端或低相对移动性的终端被称为去往多跳邻近网络的接入/中继节点。
终端例如是车辆、便携式电话、计算机。静态终端或低相对移动性的终端是固定车辆。
附图说明
-图1a和1b示出了符合可能实施方式的通信系统的通用架构;
-图2a和2b示出了CDS和MIS的概念;
-图3a-3c示出了根据本发明的算法的示例实施方式的阶段1(MIS的计算);
-图4a至图4d示出了相同算法的阶段2(mDS的计算);
-图5示出了感兴趣区域和无线电覆盖范围约束的分数计算的实例;
-图6a,6b和7a至7c示出了相同算法的阶段3a和3b;
-图8a,8b示出了这些步骤的另一变型实施方式;
-图9a,9b和10a,10b示出了相同算法的第四阶段;
-图11至13a-13g示出了具有相同算法的另一实施例;
-图14a,14b和14c给出了网络雾的尺寸结果,其中根据节点离开的数量(图14a)、要覆盖的感兴趣区域的尺寸(图14b)或甚至是根据要覆盖区域的数量(图14c)来获得网络雾的尺寸结果。
具体实施方式
图1a示出了根据可能实施方式的通信系统的通用架构。
这个通用架构包括四个独立的层:
-所谓的“最终用户”层1,
-形成具有动态架构的多跳虚拟邻近网络的节点的层2,
-接入层3,包括通信网络的经典装置,例如蜂窝网络或WiFi网络,
-包含控制器6的云层4。
“最终用户”层1由包括通信装置5(便携式电话、计算机、车辆连接的仪表板或任何其它适合的通信装置)的终端构成。
这些通信终端5特别地包括三个接口:
-一个接口用于当终端靠近(范围小于或等于500米)时使终端彼此进行通信(例如,WiFi接口(IEEE 802.11n/ac/p)和/或蓝牙和/或Zigbee和/或V2X和/或C-V2X和/或DSRC等),
-另一个用于与远程资源进行通信(例如,蜂窝接口(3G/3G+/4G/LTE/5G)),
-地理位置接口(例如,通过卫星定位)。
用户预先从这些终端5下载了与他们要访问的共享服务信息相对应的应用。
例如,这个应用是用于导航和社区交通信息的应用。
利用对共享数据的访问的其它类型的服务也是可能的。尤其是,除了导航和交通信息应用之外或与导航和交通信息应用相独立地,服务还可以提供音乐共享服务,并且更广泛地共享各种数据:与可用的停车位相关的信息、给定商店的促销、物联网(IoT)数据等...。
通过安装应用并且在注册阶段之后,用户将成为社区的成员。然后,他可以从应用的原始服务中受益,特别是例如流量的导航和状态。根据用户在基础设施网络和社区中的贡献,可以逐步使其它服务对于用户来说是可访问的。
从终端5下载的应用在终端5上通过询问位置接口来确定,它们是否在移动,或者相反的是静止的或处于相对较低移动性的情况。
这些静态终端或低相对移动性的终端(例如,固定式车辆)(在图1a中用5A表示)用于构成虚拟网络并形成临时的且机会的网络基础结构。
当应用将终端激活,并且应用检测到它是否涉及静态或低相对移动性低的终端时,在第一种情况下,这样的终端5A在社区中通过使用WiFi接口上的“Bonjour”协议检测到其相邻的终端,这些相邻的终端也是静态的或低相对移动性的终端。
然后,它通过蜂窝或WiFi接口将消息发送到层4的控制器6,指示其地理位置,以及不同的技术参数,例如:WiFi和蜂窝连接的质量、数据存储的存储容量、其相邻终端的列表、与其它终端的连接程度、可用的电池电量等级、终端的速度、终端与动态多跳邻近网络(当创建了动态多跳邻近网络时)的连接质量、电子声誉或有关社交网络终端特性的所有者的其它信息,等等…。
当控制器6从所有低相对移动性用户接收消息时,控制器6构建用户的网状拓扑。
这个网格的节点是移动终端5A。
如果两个节点5A之间的距离小于允许两个节点5A在它们之间直接进行交换的覆盖范围的半径,则两个节点5A通过桥连接。
在这个拓扑上,控制器6执行下面将描述的算法,以确定每个用户的角色。
因此,在终端5A中:
-一些终端(在图1b中由R所表示的)将扮演中继的角色,并形成到雾的WiFi接入网络,
-其它终端(在图1b中由F所表示的)将扮演本地资源网络(雾网络)的节点的角色,
-其它终端仍将扮演网关的角色(图1b中的“网关”P),以确保将Fog连接到传统的接入网络(蜂窝、公共WiFi终端、用户的盒子……)以到达云。图3显示了这种选择的实例。
智能化选择雾网络的最小数量的节点F,但是数量足够减少网络节点之间的WiFi干扰、在流向中继用户方面提供最佳连接、提供大量存储容量、确保故障和移动性的容忍度。
应当注意的是,这个问题是NP完全组合优化的问题。算法在可接受的拟线性计算时间内找到拟最佳解。
为了达到这个目的,算法以搜索相关的最优支配组件的形式对问题进行建模。
支配节点代表Fog的节点,但同时它们也可以是中继R和/或网关P。
受支配的节点代表中继器R和/或网关P。
算法中另一个非常重要的元素是,它还监视感兴趣中心附近的Fog节点的存在(当这是可能的时),这些节点是否是永久性的、例如交叉路口、交通信号灯、道路交叉口等,还是临时的,例如音乐厅、用于体育赛事的接待处,...。
这使用户可以访问并快速地提取敏感和高密度区域中的信息,而不会阻塞雾的其余部分。
网关用户P本身确保雾网络的节点F和云之间的链接。实际上,当Fog网络没有客户端所要求的数据时,它将通过在传统网络(3G/3G+/4G/5G、WiFi等)上具有良好因特网连接的用户来查询云。
根据用户的因特网链路质量,通过算法来指定负责雾和云之间的这个中间任务的用户P。仅选择最佳链接。
由因特网接入无线技术(蜂窝或WIFI技术)的经典元素构成层3。
用户可以通过3G/3G+/4G/5G蜂窝网络或通过公共、私人或社区终端后面的WiFi连接进行连接。鉴于WiFi受到移动性问题的困扰,即虚拟网络用户(包括网关)的低相对移动性,因此倾向于WiFi连接。
控制器6是架构的枢纽。它充当各种用户设备的协调器,并允许对网络操作进行编程。
为了这个目的,控制器6托管服务器,所述服务器具有对形成虚拟主干的终端子组件的不同参数进行个性化,并且随后选择中继节点的能力,其中例如由形成算法来定义虚拟主干。可以通过云计算中的网络(或本文中的“云计算”)进行访问。数据的聚合和存储过程形成计算机云的一部分,从而允许这些服务中的一些服务在虚拟雾网络的节点F上分布。
通过SDN技术(软件网络)将这些操作投入服务,SDN技术可以在飞行中透明地配置用户的设备。
在应用的安装期间,服务器6从客户端请求授权,客户端可以随时重新定义其协作程度。
云层4的SDN控制器6确保虚拟网络层的形成和维护。
在其容量中SDN技术的选择是为了提供抽象网络层并加速其部署。
用户设备只是在实现由控制器注入的数据处理规则。
因此,在用户侧设备不需要实现路由协议。
用户还需要将应用部署在云中,以作为全球参考,并在雾中不存在时提供数据可用性。
社区中每个低相对移动性的静态用户(通过其因特网连接)周期性地将其标识符、GPS位置以及多个技术参数,例如,速度、与其它终端的连接程度、无线电覆盖范围、终端与动态多跳邻近网络的连接质量(例如,WiFi连接的质量)、蜂窝连接的质量(3G/4G/5G等)、存储容量、可用电池电量等级,或者甚至是社交网络终端特性所有者的电子声誉或其它信息,发送给SDN控制器。
根据社区用户所发送的信息,SDN控制器首先构建连接图,其中每个节点代表用户,并且如果两个用户之间的距离小于WiFi覆盖范围的半径,则两个用户之间存在网桥。
基于结果图,控制服务器(控制器6)执行下面介绍的算法,以确定支配节点的最佳子组件,并将支配节点之间进行连接以形成核心网络(FoG)(“虚拟骨干”或形成主干网的节点)-对应于下面的“黑色”节点)。
其余节点形成接入(中继)网络(对应于下面的“白色”节点)。
这些节点中的一个或多个(支配节点或受支配的节点)也被选则作为网关,以确保与云的连接。
在确定了每个用户的角色后,SDN控制器将其角色(中继F和/或雾F的节点和/或网关P及其配置(IP地址、所使用的频率等))通知每个用户。
安装在用户终端5上的SDN管理器执行配置。
托管在雾节点F中的数据可以源自云和最终用户。
在第一种情况下,相对于雾数据的地理位置,云明确地与雾数据进行共享。换句话说,云将分布在多个雾中。很显然的是,这个操作取决于雾的存储容量。
在第二种情况下,最频繁请求的请求和客户端警报也被存储在雾中。
在第一种情况下,与第二种情况一样,使用分布式哈希表(DHT)对具有数据的雾节点进行地理定位。
为了检测拓扑结构(图)中的变化,终端必须周期性地将其位置和参数发送给控制器6(参见上面已经通过实例方式给出的列表)。
当SDN控制器6检测到低相对移动性的终端的到达和/或离开时,它重新开始雾的重建。
如前已经指出的,用户可以访问的共享服务和信息可以具有不同的类型:
-实时导航辅助/地理位置定位,
-交通信息/道路安全(警告道路事故、存在危险区域、或甚至在路边存在雷达或警察等),
-多媒体内容的交换,
-下载新的移动应用,
-共享所有数据类型(音乐、可用停车位、店内促销、物联网IoT等)
-等等。
应当注意的是,ad hoc网络的构造算法已经是已知的,并且ad hoc网络的构造算法的尺寸可以最小化,尤其是那些:
ο程Cheng等,2004,程秀珍,丁敏和陈德昌。用于ad hoc网络中连接支配集的近似算法。进行中的无线Ad Hoc传感器和对等网络(TAWN)理论方面的国际研讨会,2004年。
ο(Theoleyre和Valois,2006年)THEOLEYRE,Fabrice和VALOIS,Fabrice。自组织网络的自动组织:概念和影响。2006年。
ο用于构建旨在规模最小化的自组织网络的算法。
然而,这些算法根本不考虑移动性或其它技术参数,例如流量、电池、感兴趣区域的覆盖范围、存储容量、电子声誉等。它们几乎不能用于终端网络的情况下,以及在设想的那些类型的应用中,其中每个终端自身执行算法的程度,从而大大减少了流量和电池。
下文描述的虚拟网络的节点选择算法的优点在于,它可以考虑感兴趣的区域。
在对应用所定义的技术参数施加若干约束的情况下,根据目标函数选择将用作虚拟网络节点的支配节点。
目标函数是节点数量的最小化。
强制性约束是由以下事实构成的:形成CDS,即由支配节点构成的图的顶点的连接子组件,以使所有其它节点都具有至少一个支配相邻节点。
可以根据应用来考虑对算法的技术参数的其它约束。例如,它们可以是以下内容:
-所选节点必须覆盖感兴趣区域表面的最小阈值;
-所选节点必须具有电池电量的最小阈值;
-所选节点必须具有存储容量的最小阈值;
-所选节点必须具有流量的最小阈值;
-以及更为通常地,都必须由一组选定的节点进行优化,并相对于终端的一个或多个技术参数进行优化(典型地,可以根据这些参数计算分数并将其与阈值进行比较)。
分数是结合了一个或多个技术参数的混合指标的值;从而为了在单个值中混合技术参数(被称为得分),它们必须进行转换才能在同一字段中表示(例如,在0-1区间中)。同样,这些技术参数不需要具有相同的重要性/优先级。结果是,每个技术参数具有系数,该系数表示技术参数相当于其它技术参数的重要性或差异。分数是在算法执行期间演变的一个或多个技术参数的值。它用于确定被称为黑色的支配节点;一旦这些黑色节点被修复,则它们的分数就不重要了;下一步是通过计算其它黑色节点的分数来确定其它黑色节点。
为了使用多个技术参数,在它们之间定义了优先顺序。选择节点以优化最高优先级参数并满足对其它参数的约束。在几个候选节点具有相同的技术参数值的情况下,将根据优先级通过以下技术参数进行选择,并且依此类推。同样,可以根据每批次间隔(分数计算)对技术参数(除了地理覆盖范围)进行分类,以最大程度地进行选择,并避免选择所有节点作为支配节点。
类别的实例:
-电池:3个等级:M(“中”),H(“高”),L(“低”)
-社交网络的声誉:3个等级:M(“中”),H(“高”),L(“低”)。
算法有利地考虑了感兴趣区域。
在下文中,将使用以下术语
o根据英语术语,CDS或“连接支配集”:图的顶点的连接子组件构成被称为“支配”的节点,例如图的所有其它节点(被称为“非支配”)
具有至少一个相邻的支配;图2a示出了这一点,其顶点由黑色节点组成;
o IS或根据英文术语的“独立集”:IS是图中不相邻的节点的子组合;
·MIS或“最大独立集”是具有最多节点的IS子组件。MIS用于自组织网络中的CDS构造;在图2b中用黑色节点表示MIS。
网络的节点与颜色代码相关联,颜色代码将不同的节点与不同的状态进行关联。
按照惯例,
-支配节点将与黑色相关联,
-受支配的节点将与白色相关联,
-与中间步骤相关联的节点将是所谓的灰色(在图中由点来填充节点)
-MIS节点(“最大独立集”,即图中不相邻的且具有最多节点的图的节点的子组件)将被称为红色(图中的水平散列的节点),
-算法还使用被称为黄色的节点(图中的垂直散列的节点)。
·
图3a和下面的附图说明了初始的图配置,其中包括两个代表静态或较低移动性终端的节点(从1到10)。
按照惯例,偏离图的节点都被视为“受支配的”(白色的节点)。
在第一变型实施方式中,消除了具有不遵守多个约束中的一个的分数的所有节点。
同样,如果需要对感兴趣区域(ZI)进行覆盖范围的附加约束,则根据属于ZI的节点将图分为子图。
图3a标识了两个感兴趣的区域,一个是由节点3和5形成的ZI1,另一个是由节点9和10形成的ZI2。
如图3b所示,这样的结果是两个子图:一个是由彼此连接的两个节点3和5构成的子图,以及一个是由既不在ZI1中也不在ZI2中并且也彼此连接的节点(节点1、2、4和6至8)构成的子图。
节点9和10本身彼此独立,并且不形成任何可识别的子图。
对于每个子图,控制器按如下方式计算子图的MIS:
-用红色为具有最小标识符的节点着色;
-用灰色为一跳距离的相邻节点着色,并且用黄色为两跳距离的相邻节点着色(图3b中的节点4);
-然后,只要剩下黄色节点:
-用红色为具有最小标识符的黄色节点着色;
-用灰色为一跳距离的相邻白色/黄色节点着色,并且用黄色为两跳距离的相邻白色节点着色。
在阶段1完成时,节点被着色为红色或灰色(图3b,红色节点构成MIS)。
·
在初始状态下,所有节点均为红色或灰色。
对于每个子图,控制器6执行以下处理:
a)为每个节点计算每个技术参数的分数以及所述节点的权重;节点的权重尤其等于其着色为红色的相邻节点(在图中或子图中与其连接的节点)的数量和其着色为黑色的相邻节点(在图中或子图中与其连接的节点)的数量之和减去1;权重是组合指标,并且是基于以下技术参数的值:红色节点的连接程度和支配节点(黑色节点)的组件数量。
当节点具有相同的分数值时,这个指标会将节点进行区分。
显然的是,程Cheng等人(2004年)在文章中已经介绍了这样的权重,这可能是有利的。
b)消除具有不符合多个约束中的一个的分数的所有节点;
c)假设仍然存在所有分数均大于所要求的阈值的灰色/红色节点:
1)用黑色为具有最高优先级约束的最高分数的节点着色(根据顺序、然后权重并且随后标识符,通过以下分数来推翻相等性);
2)用白色为其相邻的非黑色节点着色。
在图4a所示的实例中,目的是使每个子图中的覆盖指标最大化,每个ZI的节点必须覆盖例如超过70%的感兴趣区域。
在图中由变量S表示覆盖范围分数。
节点3最初的得分为80%,并且权重为-1,而节点5的得分为40%,并且权重为0。
因此,节点3被切换为黑色,而节点5被着色为白色。
按照相同的方式,节点9和10最初具有相同的覆盖范围约束分数S(60%)和相同的权重P(值-1)。选择两者中的一个,以切换为黑色(具有最大标识符的一个)。
同样,右侧子图的节点分数均等于0%(因为它们不在感兴趣区域中),而节点6、7和8的权重等于0,并且节点1和4的权重等于-1。节点2本身的权重等于1。因此,节点2被着色为黑色,节点1和4被着色为白色,节点6、7和8本身保持为灰色。
完成这个第一处理后,状态为图4b中指示的状态。
应当注意的是,感兴趣区域ZI1的仅5%仍可以被节点5覆盖,其余部分要么未被节点3或5覆盖,要么已经被节点3覆盖。
节点5的权重等于0。
节点10本身仍可以覆盖区域ZI
节点6至8的权重等于0,而节点1和4的权重等于-1,并且节点2的权重等于1。
为了实现区域ZI
假定已经考虑了对区域ZI
通过示例而非限制的方式,可以通过将感兴趣区域视为圆形并且将节点的无线电覆盖范围视为圆形来进行分数的计算;可以据此研究圆的重叠,并且推导支配节点。
然后,如果有必要确保感兴趣区域ZI的无线电覆盖的阈值,则对感兴趣区域ZI的无线电覆盖范围进行重新初始化,以确定其它附加的支配节点。
在图5所示的实例中,由半径为R
其中
由以下公式给出被分配给感兴趣区域ZI中的节点i的分数
当在感兴趣区域ZI k中具有最高分数的节点i被选为支配节点时,按照每三个圆形的共同重叠区域(i,j,k),来更新相同的感兴趣区域中所有非支配节点j的分数。更具体地,对于感兴趣区域ZI k中的非支配节点j,根据以下公式给出其更新的分数:
·
在阶段2的处理完成之后,控制器6在单个图中重新发送先前的子图。
对于变为与黑色节点相邻的任何灰色/红色节点,用白色为这个节点着色。
在图6a和6b所示的实例中,节点6变为白色(受支配的节点的状态)。
·
在这个阶段,控制器6创建具有剩余灰色节点的子图。
这是由图7a至7c所示的内容,其中在新的子图中隔离节点7和8。
如果需要的话,它使用黑色为剩余灰色节点中的一个的相邻红色/白色节点和与黑色分量的最接近的节点进行着色;它还使用白色为其相邻节点着色。
接下来,对于每个子图,它执行以下步骤:
a)将具有最多相邻灰色节点的灰色节点着色为黑色;
b)将其相邻节点着色为白色;
c)假设仍然存在灰色节点:
1)将具有最多相邻灰色节点的白色节点着色为黑色;
2)将其相邻节点着色为白色。
在图7c中,具有最短标识符的节点7被切换为支配状态并被着色为黑色,而节点8被切换到受支配的状态并被着色为白色。
作为变型,可以直接在偏离图上执行步骤(a),(b),(c)的处理。这在图8a和8b中示出,其中,包括两个灰色相邻节点7和8的节点1被切换到显性状态(黑色),而节点7和8则处于主导状态(白色)。
在这个阶段期间,控制器6执行以下步骤:
a)恢复整个图;
b)对于每个剩余的红色节点:
1)如果此节点在步骤3.b之后具有相邻的黑色节点,则将这个节点着色为黑色。
假设,仍然存在剩余的白色节点:
a)如果一至两个白色节点不遵守约束,则将一至两个白色节点着色(最小可能)为黑色以连接黑色组件。
这在图9a、9b和10a、10b中示出,对于图9a、9b和10a、10b,节点1以及节点4和6被切换到支配状态(黑色)。
当处理完成时,结果是支配节点的核心网络,然后将支配节点用作具有动态体系结构的虚拟多跳邻近通信网络的骨干。
在限制电池充电等级的情况下,图11中显示了另一个实例。
在所示的实例中,图包括10个节点,这些节点处于低电量等级(节点4、7和9处于等级L)或处于中电量等级(节点1、2、5、6、8)或高电量等级(节点3和10在等级H)。
约束是形成电池电量等级高于中等级M的网络。图12a至12d示出了形成MIS的不同步骤。在完成这个第一阶段后,将节点1、4、9和10切换为红色,而其它节点为灰色。
在第二阶段(图13a至13g)中,控制器6根据电池等级和节点权重来计算mDS。结果是图13g中所示的mDS结构。
假定在完成这个阶段时,没有节点处于灰色状态,则不必执行阶段3和4。
黑色节点构成支配节点的网络,然后将其用作具有动态架构的虚拟多跳邻近通信网络的骨干。
当然,可以将多个约束进行关联以确定雾网络,例如,每个感兴趣区域的覆盖率超过70%,并且每个节点的电池电量等级都高于中等级,或更一般地,可以考虑任何其它约束是有用的。
为了执行上述过程,可以对每个感兴趣区域进行分层约束。
图14a、14b和14c给出了根据离开节点的数量(图14a)、根据要覆盖的感兴趣区域的尺寸(图14b)或再次根据要覆盖的感兴趣区域的数量(图14c),来获得雾网络的尺寸结果。
如果仅对离开节点的数量(图14a)感兴趣,则在建议的过程(曲线B)和程Cheng算法(曲线C)的情况下获得的结果是相似的;然而,由于图8a和8b所示的步骤3b中的变型以及阶段1中的变型,因此所提出的过程根据用于构成网络CDS的节点能够实现时间增益,在阶段1中,消除具有不符合多个约束中的一个的分数的所有节点。
这种增益更加令人惊讶的,因为考虑比程Cheng所考虑的更多的技术参数的事实会导致先验地为网络构造更多的节点,但是,它被发明人提出的变体所补偿。
这种增益更大,因为它是从相当大的尺寸(图14b)或很多尺寸(图14c)的感兴趣区域中获取的。
机译: 允许最终用户终端在具有动态体系结构的无线多跳通信邻近网络上进行交换的方法和组件
机译: 最终用户通过动态架构的通信邻近多希望网络进行交换的方法和组件
机译: 最终用户通过动态架构的通信邻近多希望网络进行交换的方法和组件