一种针对车辆多跳通信网络的基站部署方法

摘要

本发明提供一种针对车辆多跳通信网络的基站部署方法，建立了以车辆和基站作为节点的车辆社交网络，进一步根据车辆社交网络的属性，将优化的目标函数从提升车辆多跳通信网络的传输成功率转换成了从候选的基站位置集合中选择一个较优解，能够解决现有基站部署方法在针对车辆多跳通信网络时的不足，实现高传输性能的车辆间多跳通信。

权利要求

1.一种针对车辆多跳通信网络的基站部署方法，其特征在于，包括以下步骤：

(1)建立车辆社交网络，所述车辆社交网络中的每个节点代表车辆或者候选的基站位置，每个边代表车辆与车辆间或者车辆与候选的基站位置间的历史相遇情况；

(2)初始化：将所有的候选的基站位置设为一个候选集合，将所有的已选择的基站位置设为一个已选集合，并将已选集合设置为空集；

(3)根据所述车辆社交网络中的节点和边计算每一个候选的基站位置的优越性，并将优越性最高的候选的基站位置从候选集合中删除并添加到已选集合中，同时车辆社交网络被更新；步骤(3)的具体过程包括：根据所述车辆社交网络中的节点和边计算每一个候选的基站位置添加至已选集合后的整体的中心性值较添加该候选的基站位置前整体的中心性值的增量，增量越大，优越性越高；

选择出所述增量最大的候选的基站位置，将其加入到已选集合中，并更新所述整体的中心性值，并将增量最大的候选的基站位置从候选集合中去除；

(4)判断已选集合中的基站位置数量是否达到基站部署的预设限制数量，若否，则返回步骤(3)，继续选择优越性最高的候选的基站位置添加至已选集合中；若是，则执行步骤(5)；

(5)按照已选集合中的基站位置部署基站；

其中，步骤(1)中的车辆社交网络的边是用权值表示的，以区分不同的相遇频率所造成的不同的通信能力，边的权值和两节点的相遇次数相关，即随着相遇次数的增加，权值应当增加，但同时随着相遇次数的增加，权值增加的量不断减少，步骤(1)中的车辆社交网络的边采用权值公式(1-λn)/(1-λ)的计算值来表示，其中n表示相遇的次数，λ为一个权值调整的参数，0<λ<1，步骤(3)中更新所述整体的中心性值时，采用度作为度量，且当已选集合中不同基站连接了同一个车辆节点时，将所述连接合并成车辆社交网络的一个新的边，该新的边的权值由权值公式(1-λn)/(1-λ)算出，其中n为所述不同基站与同一个车辆节点相遇的次数和，步骤(3)中更新所述整体的中心性值时，采用特征向量作为度量，单个节点的中心性值是所有直接连接的邻居节点中心性值与相应边的权值的乘积之和，整体的中心性值通过添加的该候选的基站位置这一节点的中心性值与添加该候选的基站位置前整体的中心性值迭代而得出。

2.如权利要求1所述的针对车辆多跳通信网络的基站部署方法，其特征在于，步骤(2)中初始化过程还包括：定义已选集合的所有基站位置的整体的中心性值，并将所述整体的中心性值的初始值设为0。

3.如权利要求2所述的针对车辆多跳通信网络的基站部署方法，其特征在于，迭代而得出所述整体的中心性值之前，合并连接相同车辆节点的边，合并后的边的权值由权值公式(1-λn)/(1-λ)算出，其中n为不同基站与同一个车辆节点相遇的次数和。

说明书

一种针对车辆多跳通信网络的基站部署方法

技术领域

[0001] 本发明涉及无线车辆网络通信技术领域，尤其涉及一种针对车辆多跳通信网络的基站部署方法。

背景技术

[0002] 无线车辆网络是一种新型的车辆通信网络。当给车辆装载了无线通信设备之后，车辆本身可以和附近一定范围内的其他车辆或者路边基础设施进行无线通信，通信的数据还可以储存在车辆的缓存中。为了实现车辆间的多跳通信，即车辆到车辆的数据包传输通信，车辆网络需要采用“储存-运输-转发”的策略。在城市中，可以通过车辆间的通信来传递路况信息、也可以帮助司机避免潜在的碰撞事故，当道路发生紧急事件后也可以利用车辆网络将信息传播到其他地方，还可以实现自动过路收费、停车点信息传播、发布广告等。然而由于车辆网络自身的特点：（1）车辆运动的不确定性导致迅速变化的拓扑结构（2）任意时刻往往不存在从源车辆节点到目的车辆的节点的完整传输路径。车辆网络中的多跳通信往往是高丢包率和高延迟的。研究表明，在路边部署基站的方法能够显著的提升车辆网络中的多跳通信性能。基站能够和附近的车辆进行通信，也能够和其他的基站进行有线通信，包括利用互联网。基站本身也具有很大的缓存用来储存数据。

[0003] 由于基站的成本较高，需要使得部署的一定数量的基站拥有最大的提升效果。基站部署的位置与提升效果的关系最为密切。虽然目前已有很多基站部署方法，例如针对车辆传感器网络的部署方法、针对公共交通的基站部署方法和简单利用地理位置信息的方法，但是这些已有方法均不适用针对车辆间的多跳通信的基站部署。例如：针对车辆传感器网络的部署方法可以直接建立车辆轨迹与数据包收集之间的关系，但车辆传感器网络中的数据只涉及到一跳传输，即从车辆到基站，而车辆多跳通信网络中的关系和数据则复杂得多，显然针对车辆传感器网络的部署方法不适用针对车辆间的多跳通信的基站部署；针对公共交通的部署算法是完全已知车辆的运动规律的，与多跳通信网络中的车辆运动随机性并不同，显然也不适用针对车辆间的多跳通信的基站部署；利用地理位置信息的部署方法，通常是考察道路的流量信息，然后确定出一些的车流经过的热点，在热点出部署基站，然而根据这些流量信息确定的热点彼此间往往很接近，会造成基站的重复部署，显然也不适用针对车辆间的多跳通信的基站部署。

[0004] 因此，需要一种新的专门针对车辆多跳通信网络的基站部署方法，能够避免现有基站部署方法在针对车辆多跳通信网络时的不足，实现车辆间的多跳通信。

发明内容

[0005] 本发明的目的在于提供一种针对车辆多跳通信网络的基站部署方法，能够解决现有基站部署方法在针对车辆多跳通信网络时的不足，实现高传输性能的车辆间多跳通信。

[0006] 为解决上述问题，本发明提供一种针对车辆多跳通信网络的基站部署方法，包括以下步骤：

[0007] （1）建立车辆社交网络，所述车辆社交网络中的每个节点代表车辆或者候选的基站位置，每个边代表车辆与车辆间或者车辆与候选的基站位置间的历史相遇情况；

[0008] （2）初始化：将所有的候选的基站位置设为一个候选集合，将所有的已选择的基站位置设为一个已选集合，并将已选集合设置为空集；

[0009] （3）根据所述车辆社交网络中的节点和边计算每一个候选的基站位置的优越性，并将优越性最高的候选的基站位置从候选集合中删除并添加到已选集合中，同时车辆社交网络被更新；

[0010] （4）判断已选集合中的基站位置数量是否达到基站部署的预设限制数量，若否，则返回步骤（3），继续选择优越性最高的候选的基站位置添加至已选集合中；若是，则执行步骤（5）；

[0011] （5）按照已选集合中的基站位置部署基站。

[0012] 进一步的，步骤（1）中的车辆社交网络的边是用权值表示的，以区分不同的相遇频率所造成的不同的通信能力，边的权值和两节点的相遇次数相关，即随着相遇次数的增加，权值应当增加，但同时随着相遇次数的增加，权值增加的量不断减少。

[0013] 进一步的，步骤（1）中的车辆社交网络的边采用权值公式(1-λn)/(1-λ)的计算值来表示，其中n表示相遇的次数，λ为一个权值调整的参数，0<λ<1。

[0014] 进一步的，步骤（2）中初始化过程还包括：定义已选集合的所有基站位置的整体的中心性值，并将所述整体的中心性值的初始值设为0。

[0015] 进一步的，步骤（3）的具体过程包括：

[0016] 根据所述车辆社交网络中的节点和边计算每一个候选的基站位置添加至已选集合后的整体的中心性值较添加该候选的基站位置前整体的中心性值的增量，增量越大，优越性越高；

[0017] 选择出所述增量最大的候选的基站位置，将其加入到已选集合中，并更新所述整体的中心性值，并将增量最大的候选的基站位置从候选集合中去除。

[0018] 进一步的，步骤（3）中更新所述整体的中心性值时，采用度作为度量，且当已选集合中不同基站连接了同一个车辆节点时，将所述连接合并成车辆社交网络的一个新的边，该边的权值由权值公式(1-λn)/(1-λ)算出，其中N为所述不同基站与同一个车辆节点相遇的次数和。

[0019] 进一步的，步骤（3）中更新所述整体的中心性值时，采用特征向量（eigenvector）作为度量，单个节点的中心性值是所有直接连接的邻居节点中心性值与相应边的权值的乘积之和，整体的中心性值通过添加的该候选的基站位置这一节点的中心性值与添加该候选的基站位置前整体的中心性值迭代而得出。

[0020] 进一步的，迭代而得出所述整体的中心性值之前，合并连接相同车辆节点的边，合并后的边的权值由权值公式(1-λn)/(1-λ)算出，其中n为所述不同基站与同一个车辆节点相遇的次数和。

[0021] 与现有技术相比，本发明的针对车辆多跳通信网络的基站部署方法具有以下有益效果

[0022] 1、采用了车辆网络的社交属性，基于该属性利用了社交网络的原理，改变了基站部署优化的目标函数，降低了方法设计的困难度；

[0023] 2、通过计算每一个候选的基站位置的优越性并择出优越性最高的候选的基站位置来部署基站，即从候选的基站位置集合中选择一个较优解（位置子集合），进而可以快速将基站部署于这些位置上并可以获得更大的性能提升；

[0024] 3、本发明的技术方案基于社交网络中的中心性原理，进一步将优化的目标函数从提升车辆多跳通信网络的传输成功率转换成了提升基站整体的中心性值，能够解决现有基站部署方法在针对车辆多跳通信网络时的不足，实现高传输性能的车辆间多跳通信。

附图说明

[0025] 图1是本发明具体实施例的针对车辆多跳通信网络的基站部署方法的流程图；

[0026] 图2是本发明具体实施例的车辆社交网络示意图；

[0027] 图3是本发明具体实施例的车辆社交网络的边的权值与相遇次数的关系。

具体实施方式

[0028] 本发明的核心思想是公开一种针对车辆多跳通信网络的基站部署方法，建立以车辆和基站作为节点的车辆社交网络，根据车辆社交网络的属性，将优化的目标函数从提升车辆多跳通信网络的传输成功率转换成了从候选的基站位置集合中选择一个较优解（位置子集合，即已选集合），能够解决现有基站部署方法在针对车辆多跳通信网络时的不足，实现高传输性能的车辆间多跳通信。

[0029] 为使本发明的目的、特征更明显易懂，下面结合附图对本发明的具体实施方式作进一步的说明，然而，本发明可以用不同的形式实现，不应认为只是局限在所述的实施例。

[0030] 请参考图1，本发明提供一种针对车辆多跳通信网络的基站部署方法，包括以下步骤：

[0031] （1）建立车辆社交网络，网络中的节点代表车辆或者候选的基站位置，网络中的边表示车辆与车辆间或者车辆与候选的基站位置间的历史相遇情况。如图2中，空心点21代表候选的基站位置，实心点20代表车辆节点，斜线填充的点22代表已选择的基站位置；

[0032] （2）初始化：将所有的候选的基站位置设为一个候选集合，将所有的已选择的基站位置设为一个已选集合，并将已选集合设置为空集，同时将已选集合所有基站位置的整体的中心性值设为0；

[0033] （3）根据所述车辆社交网络中的节点和边计算每一个候选的基站位置对已选集合的整体的中心性可能的增量，即假设选择一候选的基站位置作为基站的部署位置，或者说假设这一候选的基站位置添加到已选集合中，此时新的已选集合的整体的中心性值较之前（未添加这一候选的基站位置时）的增量，由于初始值设置为0，因此，第一轮计算时假设的新的已有集合的整体的中心性值就是增量，后面的循环后要比较与之前一轮的整体的中心性值的增量；

[0034] 即本实施例中每一个候选的基站位置的优越性用整体的中心性值来表示，由此选择出增量最大的候选的基站位置，将其加入到已选集合中，更新已选集合的整体的中心性值，并将增量最大的候选的基站位置从候选的基站位置集合中去除；

[0035] （4）判断已选集合中的基站位置数量是否达到基站部署的预设限制数量，如果已选集合中基站位置的数量小于基站部署的预设限制数量，则返回步骤（3）继续添加待部署的基站位置；

[0036] （5）如果已选集合中的基站位置数量已经达到基站部署的预设限制数量，则按照已选集合中的基站位置部署基站。

[0037] 本实施例中，步骤（1）中的车辆社交网络的边是用权值表示的，用以区分不同的相遇频率所造成的不同的通信能力，边的权值应当和网络中两节点的相遇次数相关，即随着相遇次数的增加，权值应当增加，但同时随着相遇次数的增加，权值增加的量应当不断减少，因此可以使用(1-λn)/(1-λ)这样的函数，其中n表示相遇的次数，λ为一个权值调整的参数，0<λ<1。

[0038] 本实施例中，步骤（3）中的已选集合的整体的中心性计算方法根据不同的中心性度量有不同的定义：

[0039] 当度（degree）作为度量时，单个节点的中心性值为该点所连接的所有的边的权值的和。已选集合的整体的中心性值略有不同，在计算整体的中心性值之前需要将车辆社交网络的一些边合并，即当已选集合中不同的基站（基站位置）连接了同一个车辆节点时，需要合并成一个新的边，该边的权值由权值公式(1-λn)/(1-λ)算出，其中的相遇次数n为基站与该车相遇的次数和。合并的边的权值会小于合并前的边的权值的和。

[0040] 当用特征向量（eigenvector）作为度量时，单个节点的中心性值是所有直接连接的邻居节点中心性值与相应边的权值的乘积之和，而整体的中心性值通过添加的该候选的基站位置这一节点的中心性值与添加该候选的基站位置前整体的中心性值迭代而得出。这里涉及到迭代的过程，为了简化计算，我们只迭代两次。初始时，设所有的节点的中心性值为1，第二次计算在第一次计算的结果基础上进行。同样，已选集合的整体的中心性值计算前需要合并连接了相同车辆节点的边。合并后的边的权值由权值公式(1-λn)/(1-λ)算出，其中n为所述不同基站与同一个车辆节点相遇的次数和。

[0041] 综上所述，本实施例提供的针对车辆多跳通信网络的基站部署方法，基于社交网络中的中心性原理，建立了以车辆和基站作为节点的车辆社交网络，根据车辆社交网络的属性，将优化的目标函数从提升车辆多跳通信网络的传输成功率转换成了提升基站整体的中心性值，能够解决现有基站部署方法在针对车辆多跳通信网络时的不足，实现高传输性能的车辆间多跳通信。

[0042] 显然，本领域的技术人员可以对发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。