[0047] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。
[0048] 下面参照附图描述根据本发明实施例提出的城市车载网中路边单元的部署和调度方法及装置，首先将参照附图描述根据本发明实施例提出的城市车载网中路边单元的部署和调度方法。
[0049] 图1是本发明一个实施例的城市车载网中路边单元的部署和调度方法的流程图。
[0050] 如图1所示，该城市车载网中路边单元的部署和调度方法包括以下步骤：
[0051] 步骤S1，根据每个交叉路口的预设优先级在目标区域范围内选择多个目标交叉路口，并根据多个目标交叉路口部署多个路边单元。
[0052] 可以理解的是，如图2所示，首先基于优先级在整个城市范围内选择合适的交叉路口来部署路边单元，使得路边单元尽量少，并且通信范围覆盖所有交叉路口。
[0053] 其中，预设优先级即为交叉路口的优先级，是由该路口通过的车流密度和该路口与其他路口的连接性决定，其中路口的连接性又由该路口与其他路口之间的直接路径数决定。交叉路口优先级的影响因子值应该为原始值经过归一化之后的值，其取值范围控制在0-1之间。
[0054] 需要说明的是，目标交叉路口即为部署路边单元的交叉路口，本发明实施例中，将部署路边单元的交叉路口集合记为VR，在第i个交叉路口部署就记为vR_i，并且 将已部署的路边单元所覆盖的交叉路口集合记为CR，其中第i个交叉路口部署的路边单元的交叉路口覆盖集记为CR(vi)。临时部署路边单元交叉路口的集合记为TVR，临时部署路边单元所覆盖的交叉路口集合记为TCR。
[0055] 进一步地，在本发明的一个实施例中，预设优先级的计算公式为：
[0056]
[0057] 其中， min(Xveh)表示集合Xveh中元素的最小值，max(Xveh)表示集合Xveh中元素的最大值，min(Xcon)表示集合Xcon中元素的最小值，max(Xcon)表示集合Xcon中元素的最大值。
[0058] 在本发明的一个实施例中，两个影响因子 和 所占的权重分别记为wveh和wcon，其中，wveh+wcon＝1。
[0059] 需要说明的是，本发明实施例将所有交叉路口作为路边单元的候选部署位置，交叉路口的位置集合记为V＝{v1,v2…vi…}，任意交叉路口节点记为vi，其中i＝1,2,3…n。将交叉路口的优先级集合记为P＝{p1,p2,…pi…}，其中交叉路口vi的优先级记为pi，将影响交叉路口优先级的车流密度影响因子记为fveh，交叉路口vi的车流密度影响因子记为 影响交叉路口优先级的路口连接性影响因子记为fcon，交叉路口vi的路口连接性影响因子记为 是第i个路口的车流密度影响因子的原始值即交叉路口vi的车流量值， 是第i个路口的连接性影响因子的原始值即交叉路口vi与之相连的路口数量值；Xveh是所有路口车流密度影响因子原始值的集合，Xcon是所有路口连接性影响因子原始值的集合；将两个影响因子 和 所占的权重分别记为wveh、wcon，并且wveh+wcon＝1。
[0060] 进一步地，在本发明的一个实施例中，步骤S1进一步包括：
[0061] 步骤S11，将目标交叉路口集合VR和路边单元覆盖的交叉路口集合CR均初始化为空；
[0062] 步骤S12，根据每个交叉路口的预设优先级降序排列每个交叉路口；
[0063] 步骤S13，判断CR是否覆盖每个交叉路口，如果否，则循环执行步骤S14至步骤S17；
[0064] 步骤S14，将VR的值赋给预设目标交叉路口集合TVR，并将CR的值赋值给预设路边单元覆盖的交叉路口集合TCR；
[0065] 步骤S15，选择预设优先级最高的交叉路口vi，其中，vi∈V-VR，V为所有交叉路口的集合，判断交叉路口vi是否满足预设条件，如果满足则VR中加入vi，CR中加入集合CR(vi)，CR(vi)为第i个交叉路口部署的路边单元的覆盖的交叉路口集合，并执行步骤S16，如果不满足，则根据每个交叉路口的预设优先级降序的顺序依次找到满足预设条件的交叉路口为止，并执行步骤S15，其中，预设条件为交叉路口vi不在CR范围内；
[0066] 步骤S16，对于交叉路口vl，其中，vl∈CR(vi)-TCR，如果pi-pl在预设阈值范围内，则保留交叉路口vl并进入步骤S17，否则抛弃交叉路口vl，继续执行步骤S16，如果TCR∪CR(vl)集合中的元素个数大于CR集合中的元素个数，则保留该路口vl并进入步骤S17，否则继续执行步骤S16，其中，交叉路口vi的预设优先级记为pi，交叉路口vl的预设优先级记为pl；
[0067] 步骤S17，在所有vl∈CR(vi)-TCR均判断完毕之后，结束步骤S16，并选出TCR∪CR(vl)集合对应的最大交叉路口vl；
[0068] 步骤S18，将集合VR替换为TVR∪vl，集合CR替换为TCR∪CR(vl)，结束步骤S14，以完成VR中包含的每个目标交叉路口对应的路边单元的部署。
[0069] 具体而言，如图3所示，具体包括：
[0070] 步骤1.1：pi的计算。交叉路口vi优先级的计算公式为 其中 这里min(Xveh)表示集合
Xveh中元素的最小值，max(Xveh)表示集合Xveh中元素的最大值；min(Xcon)表示集合Xcon中元素的最小值，max(Xcon)表示集合Xcon中元素的最大值。
[0071] 步骤1.2：初始化VR和CR的值，使其为空。
[0072] 步骤1.3：按照pi的降序排列所有交叉路口V。
[0073] 步骤1.4：当已部署的路边单元集合的通信范围未覆盖所有交叉路口集合时，循环执行后续步骤。
[0074] 步骤1.5：将VR的值赋给TVR，CR的值赋给TCR。
[0075] 步骤1.6：选择pi值最高的交叉路口vi，其中vi∈V-VR，做如下判断。
[0076] 步骤1.7：如果该交叉路口vi不在CR范围内，VR集合中加入vi，CR集合中加入集合CR(vi)；否则不部署，找到pi值次高的继续判断该条件直到满足为止。
[0077] 步骤1.8：对于每一个vl∈CR(vi)-TCR，循环执行下列操作。
[0078] 步骤1.9：如果pi-pl在一定的阈值范围内，则保留该路口vl进入下一步；否则抛弃，返回上一步骤。
[0079] 步骤1.10：如果TCR∪CR(vl)集合中的元素个数大于CR集合中的元素个数，则保留该路口vl进入下一步；否则抛弃，返回步骤1.8。
[0080] 步骤1.11：直到所有的vl∈CR(vi)-TCR均判断完毕，结束步骤1.8的循环；选出最大TCR∪CR(vl)集合对应的路口vl。
[0081] 步骤1.12：将集合VR替换为TVR∪vl，集合CR替换为TCR∪CR(vl)。
[0082] 步骤1.13：结束步骤1.4的循环，在VR中包含的各个交叉路口部署路边单元。
[0083] 步骤S2，根据基于密度的聚类算法在目标区域范围内识别得到每个预设时间段内的多个热点区域。
[0084] 可以理解的是，如图2所示，本发明实施例根据DBSCAN算法找到不同时刻的热点区域。其中，对于任意一个网格单元，如果其网格密度大于规定阈值，则该网格单元为一个热度网格单元。根据聚类算法，由若干个相邻的热度网格单元构成的单元群为一个热点区域，热点区域的形状不固定。另外，本领域技术人员可以根据实际情况设置预设时间段，本发明实施例以将一天24个小时按每两个小时等分成12个时间段，记为时间段t，其中t＝1,2…12，为例进行说明。
[0085] 具体而言，热点区域查找的问题转化：DBSCAN算法是一个基于密度的聚类算法，它包含两个参数：ε(搜索半径)、MinPts(邻域密度阈值)，该算法从任意的核心点出发，找出与其距离在ε之内的所有邻居点作为它的簇成员，当邻居节点的数量达到最小要求MinPts时，就形成一个簇。本发明实施例利用DBSCAN算法找出每个时间段的热点区域集合，其中网格单元密度大于α的网格单元对应DBSCAN算法中的核心点，从任意满足条件的网格单元出发，找出与其距离在ε之内的所有同样也满足条件的邻居网格单元作为它的簇成员，当邻居网格单元的数量达到最小要求MinPts时，就形成一个簇。这个簇就是本发明实施例找的其中一个热点区域。
[0086] 进一步地，在本发明的一个实施例中，步骤S2进一步包括：
[0087] 所步骤S21，将目标区域的经度跨度和纬度跨度均均分为a个跨度段，每个跨度段的跨度为b，以将目标区域分成a个大小为b×b的网格单元U(k)，其中，a、b和k均为正整数；
[0088] 步骤S22，在每个预设时间段内，根据映射到每个网格单元U(k)上的GPS数据点得到每个网格单元U(k)网格密度
[0089] 步骤S23，在每个预设时间段内，找出网格密度 的所有网格单元集合Qt，并根据基于密度的聚类算法识别得到每个预设时间段内的多个热点区域。
[0090] 步骤S23还包括：如果网格单元不满足网格密度 则标记该网格单元为噪声点。
[0091] 需要说明的是，本发明实施例将整个城市场景等分成a个大小为b×b的网格单元，其中任意一个网格单元记为U(k)。对于任意一个网格单元，映射到U(k)上的GPS数据点的总数称为网格密度dU(k)，任意时间段的任意网格单元密度记为 并将所有 的网格单元的集合即任意时间段t网格密度dU(k)≥α的网格单元集合记为Qt。将任意时间段t的热点区域集合记为 其中 为时间段t的第g个热点区域。
[0092] 步骤S3，根据每个预设时间段内的多个热点区域调度处于热点区域范围内的路边单元进行工作。
[0093] 可以理解的是，在指定时间段内调控热点区域内路边单元的工作状态和休眠状态，以确保所有路边单元消耗的总能量尽量小，同时维持城市车载网系统的网络连通性和服务质量。
[0094] 需要说明的是，(1)任意一时间段所有路边单元组成的系统对车辆请求的服务质量用当前时间段处于工作状态的路边单元所覆盖的车辆数(即在这些路边单元的通信范围内的车辆数)与当前时间段内正在运行的车辆数的比值来衡量。
[0095] (2)依据网络服务需求，路边单元可以处于工作状态或休眠状态。在车辆高密度环境，车辆间通信频繁，多数路边单元需进入工作状态；反之，若在低密度环境，在不影响通信性能的前提下，路边单元可以不参与通信连接，即进入休眠状态，减少能量的消耗。
[0096] (3)路边单元处于休眠状态以及状态转换时不消耗能量。
[0097] (4)将一天24个小时平均分成12个时间段，每两个小时为一个时间段，并且每个时间段路边单元调度方案不变，即路边单元处于工作或休眠的状态不变。
[0098] (5)将任意时间段t处于工作状态的路边单元集合记为Xt。
[0099] 进一步地，在本发明的一个实施例中，步骤S3进一步包括：
[0100] 步骤S31，设置基于密度的聚类算法的搜索半径为ε和邻域密度阈值为MinPts，并初始化每个预设时间段内的热点区域集合St为空，在每个预设时间段内均执行以下步骤；
[0101] 步骤S32，标记集合Qt中所有网格单元为未被搜索网格单元；
[0102] 步骤S33，从集合Qt中任意选择一个未被搜索网格单元U(k)，并执行步骤S34至步骤S37；
[0103] 步骤S34，标记未被搜索网格单元U(k)为已搜索网格单元，如果已搜索网格单元U(k)的搜索半径范围内至少有MinPts个集合Qt中的元素，则创建一个热点区域 并把已搜索网格单元U(k)添加到 中；否则将其标记为噪声点；
[0104] 步骤S35，将已搜索网格单元U(k)半径范围内的在集合Qt中的其他网格单元加入集合N中，并对集合N中每一个未被搜索的网格单元U(k′)∈N，执行步骤S36；
[0105] 步骤S36，将未被搜索的网格单元U(k′)标记为已搜索网格单元，如果U(k′)的搜索t半径范围内至少有MinPts个集合Q中的元素，则这些元素添加到集合N中；如果U(k′)不属于St中的任何的热点区域，则将U(k′)加入 中；否则将其标记为噪声点；
[0106] 步骤S37，直到集合Qt中所有的网格单元均被搜索，则在该预设时间段内的热点区域的集合为St；
[0107] 步骤S38，初始化所有部署的路边单元为休眠状态，对热点区域集合St中的每一个热点区域 如果部署的路边单元vR_i在热点区域 范围内，则将该路边单元设置为工作状态。
[0108] 具体而言，结合步骤S2和步骤S3，如图4所示，识别热点区域和调度路边单元的具体包括：
[0109] 步骤2.1：网格划分。根据目标区域的经纬度坐标范围，将经度和纬度坐标分成大小为b的小段，然后将整个区域分成a个大小为b×b的小区域单元，第k个小区域单元称为网格单元U(k)。
[0110] 步骤2.2：将出租车GPS轨迹数据映射到网格单元中，在每个时间段t，计算每个网格单元U(k)的网格密度
[0111] 步骤2.3：在每个时间段t，找出网格密度 的所有网格单元集合Qt，对应聚类算法中的核心点对象集合，并作为下一步骤的输入之一，其他不满足条件的网格单元标记为噪声点。
[0112] 步骤2.4：设置聚类算法中的搜索半径ε和邻域密度阈值MinPts，初始化每个时间t段的热点区域集合S为空。按时间段的划分，对于每一个时间段t循环执行所有下列操作。
[0113] 步骤2.5：标记集合Qt中所有网格单元为未被搜索(UNSEARCH)。
[0114] 步骤2.6：从集合Qt中随机选择一个UNSEARCH的网格单元U(k)，执行步骤2.7到步骤2.12。
[0115] 步骤2.7：将该U(k)标记为已被搜索(SEARCHED)。
[0116] 步骤2.8：如果U(k)的搜索半径范围内至少有MinPts个集合Qt中的元素，则创建一个新的热点区域 并把U(k)添加到 中；否则将其标记为噪声点。
[0117] 步骤2.9：将U(k)搜索半径范围内的在集合Qt中的其他网格单元加入一个新的集合N中。
[0118] 步骤2.10：对每一未被搜索的U(k′)∈N，执行步骤2.11。
[0119] 步骤2.11：将该U(k′)标记为已被搜索(SEARCHED)，如果U(k′)的搜索半径范围内至少有MinPts个集合Qt中的元素，把这些元素添加到集合N中；如果U(k′)不属于St中的任何的热点区域，则将U(k′)加入 中；否则将其标记为噪声点。
[0120] 步骤2.12：直到集合Qt中所有的网格单元均被搜索，集合St即为在时间段t内热点区域集合。
[0121] 步骤2.13：初始化所有部署的路边单元为休眠状态。对热点区域集合St中的每一个热点区域 做以下判断。
[0122] 步骤2.14：如果部署的路边单元vR_i在热点区域 范围内，就将该路边单元设置为工作状态。
[0123] 根据本发明实施例提出的城市车载网中路边单元的部署和调度方法，通过路边单元的部署和调度以确保整个路边单元系统所消耗的总能量尽量小，通过路边单元的部署，同时考虑优先级和均匀性，保证了车载网络的服务性能，通过热点区域的识别，针对不同时间段不同区域车流量的分布不均匀问题，对路边单元进行有效的调度，从而在不影响连接和服务质量的前提下，在指定时间段内调控路边单元的工作状态和休眠状态，提高了车载网络的能量资源利用率。
[0124] 其次参照附图描述根据本发明实施例提出的城市车载网中路边单元的部署和调度装置。
[0125] 图5是本发明一个实施例的城市车载网中路边单元的部署和调度装置的结构示意图。
[0126] 如图5所示，该城市车载网中路边单元的部署和调度装置100包括：部署模块110、识别模块120和调度模块130。
[0127] 其中，部署模块110用于根据每个交叉路口的预设优先级在目标区域范围内选择多个目标交叉路口，以根据多个目标交叉路口部署多个路边单元。识别模块120用于根据基于密度的聚类算法在目标区域范围内识别得到每个预设时间段内的多个热点区域。调度模块130用于根据每个预设时间段内的多个热点区域调度处于热点区域范围内的路边单元进行工作。本发明实施例的装置100可以在不影响连接和服务质量的前提下，在指定时间段内调控路边单元的工作状态和休眠状态，提高了车载网络的能量资源利用率。
[0128] 需要说明的是，前述对城市车载网中路边单元的部署和调度方法实施例的解释说明也适用于该实施例的城市车载网中路边单元的部署和调度装置，此处不再赘述。
[0129] 根据本发明实施例提出的城市车载网中路边单元的部署和调度装置，通过路边单元的部署和调度以确保整个路边单元系统所消耗的总能量尽量小，通过路边单元的部署，同时考虑优先级和均匀性，保证了车载网络的服务性能，通过热点区域的识别，针对不同时间段不同区域车流量的分布不均匀问题，对路边单元进行有效的调度，从而在不影响连接和服务质量的前提下，在指定时间段内调控路边单元的工作状态和休眠状态，提高了车载网络的能量资源利用率。
[0130] 此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。
[0131] 在本发明中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。
[0132] 在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。
[0133] 尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。
