利用车辆自组网络减少3G共享数据下载的方法及系统

摘要

本发明公开了一种利用车辆自组网络减少3G共享数据下载的方法及系统，该方法包括如下步骤：系统初始化，获取车辆历史相遇信息以及需要下载的数据信息，同时获取需要这些数据的车辆集合；确定多阶段策略需要执行的次数；基于车辆相遇的历史信息，结合传输要求和当前传输情况计算下载策略，刻画出3G下载的最优化问题，求解该优化问题并做出相应的下载决定，通过3G下载的数据再通过车辆网络传输给需要该数据的车辆节点，并根据确定的执行次数，重复本步骤；以及所有未获取数据的车辆节点通过3G下载相应数据，通过本发明，可以既降低3G下载的花费，又满足数据传输的时效要求。

说明书

技术领域

本发明关于一种3G数据下载的方法及系统，特别是涉及一种利用车辆自组 网络减少3G共享数据下载的方法及系统。

背景技术

车辆网络是近年来新兴的网络，各国用于车辆网络的Dedicated Short Range Communications(专用短程通信技术)的标准也在制定和改善中。车辆自组织网 络是由车辆节点组成，通过车辆上安装的无线通信设备进行无线通信，收发数 据以实现车辆间、车辆与固定基础设施间的多跳无线通信，构建成一个能够完 成点到点通信的无线移动网络。在该网络中，每辆车都是整个网络的路由节点， 因此实现整个城市中车辆的互联。车辆网络的缺点是覆盖范围小，网络连接情 况不稳定，传输时延高。优点是花费基本可以忽略，传输速率高。

第三代移动通信网络(3rd-generation，3G)已经在当今被广泛的使用。移 动设备，如笔记本电脑、智能手机都配备3G模块实现高速度、广范围的无线通 信。3G通信具有通信范围广，速度快等优点。然而，由于资费较贵导致用户不 能随意的下载而必须考虑资费问题。

多网络混合网络模型在学术和实践领域被多次讨论。这里讨论的系统是 3G、车辆混合网络，车辆网络中的车辆节点不仅可以通过短距离通信完成数据 传输，还可以接入3G模块进行数据下载(比如下载地图更新信息等)。其解决 如下场景的问题：车辆网络中的一个子集合需要下载相同的数据，这类数据一 开始只能通过3G网络下载。由于3G下载需要支付运营商一定的费用，所以成 本最高的方法是集合中的每一辆车通过3G各自下载，这种方法花费最大但是时 延最小。另外一个方法是集合中的单个节点通过3G下载数据，然后再通过车辆 网络传递给集合中的其他车辆节点。这种方法虽然花费最小，但是由于车辆网 络传输延迟较高，导致部分节点不能在一定的时效内收到需要下载的数据。

发明内容

为克服上述现有技术的不足，本发明之目的在于提供一种利用车辆自组网 络减少3G共享数据下载的方法及系统，其结合车辆自组网络辅助3G下载，实 现既降低3G下载的花费，又满足数据传输的时效要求的目的。

为达上述及其它目的，本发明提供了一种利用车辆自组网络减少3G共享数 据下载的系统，至少包括：

初始化模组，用于系统初始化，获取车辆历史相遇信息以及需要下载的数 据信息，同时获取需要这些数据的车辆集合；

执行次数确定模组，用于确定多阶段策略需要执行的次数；

下载策略计算及处理模组，根据确定的执行次数，重复如下过程：基于车 辆相遇的历史信息，结合传输要求和当前传输情况计算下载策略，刻画出3G下 载的最优化问题，求解该优化问题并做出相应的下载决定，通过3G下载的数据 再通过车辆网络传输给需要该数据的车辆节点；以及

3G下载模组，在到达下载要求的时效限制的最后时刻之前，令所有未获取 数据的车辆节点通过3G网络下载相应数据。

进一步地，该下载策略计算及处理模组还包括：

传输情况收集模组，用于收集传输情况；

权重更新模组，根据收集到的当前网络的传输情况以及车辆节点本地缓存 信息，更新待选种子节点的权重；

最优化问题刻画模组，将下载问题规划成最优化问题，目标是最小化通过 3G下载的数据量，约束是每个车辆节点要在时间约束前获取需要下载的数据， 并求解该最优化问题，得到近似最优解；

数据传输模组，利用车辆自组网络的传输能力，使用两跳传输将数据在车 辆网络中传输。

进一步地，该传输情况包括每个车辆节点的缓存中需要传输的数据包的个 数以及已经传输成功的数据包。

进一步地，该最优化问题刻画模组通过如下方式将下载问题规划成最优化 问题：

最小化：$\underset{u_i\in U}{\Sigma }\underset{p_k\in P}{\Sigma }{X}_i^{\left(k\right)}$

约束于：$\frac{\left|\right|W_{\mathrm{avg}}\left(k\right)\left(T\right)\left|\right|}{\left|\right|W_c\left|\right|}·\mathrm{Cos}\_\mathrm{Sim}(W_{\mathrm{avg}}\left(k\right)\left(T\right),W_c)\ge 1-\delta$

W_c＝{ε，ε，ε，...}

将车辆网络中的车辆表示为一个集合V＝{v₁，v₂，v₃，...，v_n}，其中V的一个 子集合U＝{u₁，u₂，u₃，...，u_m}为需要下载数据包的车辆标识符，集合 P＝{p₁，p₂，...，p_k}代表需要下载的数据包，表示车辆u_i下载 数据p_k，向量$W^{\left(k\right)}\left(T\right){=}_{u_j\in U}(\underset{u_i\in S^{\left(k\right)}}{\Pi }{W}_{i1}^{\left(k\right)}T,...,\underset{u_i\in S^{\left(k\right)}}{\Pi }{W}_{\mathrm{ij}}^{\left(k\right)}T),$$W_{\mathrm{avg}}^{\left(k\right)}\left(T\right)=\frac{1}{\left|P\right|}\underset{k\in P}{\Sigma }{W}^{\left(k\right)}\left(T\right).$

进一步地，该最优化问题刻画模组通过贪心算法求解该最优化问题。

为达到上述及其他问题，本发明还提供一种利用车辆自组网络减少3G共 享数据下载的方法，包括如下步骤：

步骤一，系统初始化，获取车辆历史相遇信息以及需要下载的数据信息， 同时获取需要这些数据的车辆集合；

步骤二，确定多阶段策略需要执行的次数；

步骤三，基于车辆相遇的历史信息，结合传输要求和当前传输情况计算下 载策略，刻画出3G下载的最优化问题，求解该优化问题并做出相应的下载决定， 通过3G下载的数据再通过车辆网络传输给需要该数据的车辆节点，并根据步骤 二确定的执行次数，重复本步骤；以及

步骤四，在到达下载要求的时效限制T的最后时刻之前，所有未获取数据 的车辆节点通过3G下载相应数据。

进一步地，步骤三还包括如下步骤：

收集传输情况；

根据收集到的当前网络的传输情况以及车辆节点本地缓存信息，更新待选 种子节点的权重；

将下载问题规划成最优化问题，目标是最小化通过3G下载的数据量，约 束是每个车辆节点要在时间约束前获取需要下载的数据，并求解该最优化问题， 得到近似最优解；以及

利用车辆自组织网络的传输能力，使用两跳传输将数据在车辆网络中传 输。

进一步地，该收集传输情况收集的传输情况包括每个车辆节点的缓存中需 要传输的数据包的个数以及已经传输成功的数据包。

进一步地，该将下载问题规划成最优化问题步骤通过如下方式将下载问题 规划成最优化问题，

最小化：$\underset{u_i\in U}{\Sigma }\underset{p_k\in P}{\Sigma }{X}_i^{\left(k\right)}$

约束于：$\frac{\left|\right|W_{\mathrm{avg}}\left(k\right)\left(T\right)\left|\right|}{\left|\right|W_c\left|\right|}·\mathrm{Cos}\_\mathrm{Sim}(W_{\mathrm{avg}}\left(k\right)\left(T\right),W_c)\ge 1-\delta$

W_c＝{ε，ε，ε，...}

将车辆网络中的车辆表示为一个集合V＝{v₁，v₂，v₃，...，v_n}，其中V的一个 子集合U＝{u₁，u₂，u₃，...，u_m}为需要下载数据包的车辆标识符，集合 P＝{p₁，p₂，...，p_k}代表需要下载的数据包，表示车辆u_i下载 数据p_k，向量$W^{\left(k\right)}\left(T\right){=}_{u_j\in U}(\underset{u_i\in S^{\left(k\right)}}{\Pi }{W}_{i1}^{\left(k\right)}T,...,\underset{u_i\in S^{\left(k\right)}}{\Pi }{W}_{\mathrm{ij}}^{\left(k\right)}T),$$W_{\mathrm{avg}}^{\left(k\right)}\left(T\right)=\frac{1}{\left|P\right|}\underset{k\in P}{\Sigma }{W}^{\left(k\right)}\left(T\right).$

进一步地，步骤三中利用贪心算法求解该最优化问题。

与现有技术相比，本发明一种利用车辆自组网络减少3G共享数据下载的 方法及系统基于车辆的历史相遇信息，通过选取最有利于车辆网络传输的种子 节点，充分利用车辆网络的传输能力将数据包传递给需要该数据包的目的节点， 利用车辆自组网络，达到既满足传输要求，又降低3G下载量的使用目的。

附图说明

图1为本发明一种利用车辆自组网络减少3G共享数据下载的系统的系统架 构图；

图2为本发明一种利用车辆自组网络减少3G共享数据下载的方法的步骤流 程图；

图3为本发明较佳实施例的时效示意图；

图4为本发明一种利用车辆自组网络减少3G共享数据下载的方法之较佳实 施例的步骤流程图。

具体实施方式

以下通过特定的具体实例并结合附图说明本发明的实施方式，本领域技术 人员可由本说明书所揭示的内容轻易地了解本发明的其它优点与功效。本发明 亦可通过其它不同的具体实例加以施行或应用，本说明书中的各项细节亦可基 于不同观点与应用，在不背离本发明的精神下进行各种修饰与变更。

在描述本发明之前，首先介绍本发明中用到的专有名词：

(1)3G、车辆网络混合网络：车辆作为移动节点，车上装备了车辆网络 常见的Dedicated Short Range Communications(专用短程通信技术)用于车辆之 间的通讯。同时车辆上还装备了3G接入装置用于接入现有的3G网络。

(2)车辆历史相遇信息：统计一段时间内，车辆与车辆之间相邻两次相 遇所需要时间(间隔相遇时间)。之前的研究表明，车辆之间的间隔相遇时间符 合指数分布。

(3)多阶段：在整个数据下载截止日期前，节点多次做出下载决定的次 数。

(4)种子节点：通过3G技术下载数据内容的车辆节点。

(5)下载要求：针对于每个数据，需要该数据的车辆节点必须要在指定 的时间T之前通过3G下载或者通过车辆网络获取。

图1为本发明一种利用车辆自组网络减少3G共享数据下载的系统的系统 架构图。如图1所示，本发明一种利用车辆自组网络减少3G共享数据下载的系 统，用于3G、车辆网络混合网络，至少包括：初始化模组10、执行次数确定模 组11、下载策略计算及处理模组12以及3G下载模组13。

其中初始化模组10用于系统初始化，获取车辆历史相遇信息以及需要下 载的数据编号、个数，同时获取需要这些数据的车辆集合；执行次数确定模组 11用于确定多阶段策略需要执行的次数；下载策略计算及处理模组12根据确定 的执行次数，重复如下过程：基于车辆相遇的历史信息，结合传输要求和当前 传输情况计算下载策略，刻画出3G下载的最优化问题，求解该优化问题并做出 相应的下载决定，通过3G下载的数据再通过车辆网络传输给需要该数据的车辆 节点；3G下载模组13用于在在到达下载要求的时效限制T的最后时刻之前， 令所有没有获取数据的车辆节点通过3G网络下载相应数据。

具体来说，下载策略计算及处理模组12进一步包括：传输情况收集模组 120、权重更新模组121、最优化问题刻画模组122以及数据传输模组123，传 输情况收集模组120用于收集传输情况，包括每个车辆节点的缓存中需要传输 的数据包的个数，已经传输成功的数据包等信息；权重更新模组121，根据收集 到的当前网络的传输情况以及车辆节点本地缓存信息，更新待选种子节点的权 重；最优化问题刻画模组122将下载问题规划成最优化问题，目标是最小化通 过3G下载的数据量，约束是每个车辆节点要在时间约束前获取需要下载的数 据，通过贪心算法解该最优化问题，得到近似最优解；数据传输模组123利用 车辆自组网络的传输能力，使用两跳传输将数据在车辆网络中传输。

最优化问题刻画模组122中将下载问题规划优化问题为：

最小化：$\underset{u_i\in U}{\Sigma }\underset{p_k\in P}{\Sigma }{X}_i^{\left(k\right)}$

约束于：$\frac{\left|\right|W_{\mathrm{avg}}\left(k\right)\left(T\right)\left|\right|}{\left|\right|W_c\left|\right|}·\mathrm{Cos}\_\mathrm{Sim}(W_{\mathrm{avg}}\left(k\right)\left(T\right),W_c)\ge 1-\delta$

W_c＝{ε，ε，ε，...}

(1)将车辆网络中的车辆表示为一个集合V＝{v₁，v₂，v₃，...，v_n}，其中V的 一个子集合U＝{u₁，u₂，u₃，...，u_m}为需要下载数据包的车辆标识符，集合 P＝{p₁，p₂，...，p_k}代表需要下载的数据包。表示车辆u_i下载 数据p_k。向量$W^{\left(k\right)}\left(T\right){=}_{u_j\in U}(\underset{u_i\in S^{\left(k\right)}}{\Pi }{W}_{i1}^{\left(k\right)}T,...,\underset{u_i\in S^{\left(k\right)}}{\Pi }{W}_{\mathrm{ij}}^{\left(k\right)}T)$表示其中集合表示。针对 数据包p_k，选择已被经选为数据种子节点的车辆集合S^(k)，数据包p_k到达每个目 的节点的权重。其中$W_{\mathrm{avg}}^{\left(k\right)}\left(T\right)=\frac{1}{\left|P\right|}\underset{k\in P}{\Sigma }{W}^{\left(k\right)}\left(T\right).$表示针对所有需要下载的数据，待选 种子节点权重的平均值。

(2)权重向量W中的每一项w_ij^(k)(T)表示选取u_i为种子节点下载数据包pk 在数据时效T之前到达目的节点u_j的权重。

(3)向量W_c为常量向量，可通过改变ε的值来确定要达到的传输要求， ε一般为小于1且很小的数值。

(4)表示权重向量和约束向量的长度比，Cos_Sim(X，Y)表示 求解两个向量的余弦相似度。二者的乘积要大于1-δ，表示选择的种子节点的 权重向量要尽量接近约束常量向量，以达到传输要求。

编号0中，选择下载数据p_k的种子节点的权重函数为定义如下：

该等式表示选取u_i为种子节点下载数据包p_k在时 间T到达目的节点u_j失败的概率。其中表示u_i为种子节点下载数据包p_k 通过中间中继节点v_r在时间T之前到达目的节点u_j的概率。之前的研究表明， 车辆之间的相邻两次相遇之间的间隔相遇时间服从指数分布。λ_ij是u_i和u_j间隔 相遇时间指数分布的率参数。因此可以得到从种子u_s节点，经过中继节点v_r两 跳到达目的节点u_d的概率为：

$P_{\mathrm{srd}}^{\left(k\right)}\left(T\right)=\frac{h_r^{\left(k\right)}{\lambda }_{\mathrm{rd}}}{h_r^{\left(k\right)}{\lambda }_{\mathrm{rd}}-g_s^{\left(k\right)}{\lambda }_{\mathrm{sr}}}(1-e^{-g_s^{\left(k\right)}{\lambda }_{\mathrm{sr}}T})+\frac{g_s^{\left(k\right)}{\lambda }_{\mathrm{sr}}}{g_s^{\left(k\right)}{\text{λ}}_{\mathrm{sr}}-h_r^{\left(k\right)}{\lambda }_{\mathrm{rd}}}(1-e^{-h_r^{\left(k\right)}{\lambda }_{\mathrm{rd}}T})$

其中分别为数据包p_k在单次相遇中能够被种子节点u_s和中继节点 v_r传输的平均概率，与车辆节点缓存中待传输的数据量有关，缓存信息可以通过 传输情况收集模组120获取。

图2为本发明一种利用车辆自组网络减少3G共享数据下载的方法的步骤 流程图。图3为本发明较佳实施例的时效示意图。配合图2及图3所示，本发 明一种利用车辆自组网络减少3G共享数据下载的方法，用于3G、车辆网络混 合网络，包括如下步骤：

步骤201，系统初始化，获取车辆历史相遇信息以及需要下载的数据编号、 个数，同时获取需要这些数据的车辆集合。

步骤202，确定多阶段策略需要执行的次数。

步骤203，基于车辆相遇的历史信息，结合传输要求和当前传输情况计算 下载策略，刻画出3G下载的最优化问题，求解该优化问题并做出相应的下载决 定，通过3G下载的数据再通过车辆网络传输给需要该数据的车辆节点，并根据 步骤202确定的执行次数，重复本步骤。

步骤204，在到达下载要求的时效限制T的最后时刻之前，所有没有获取 数据的车辆节点通过3G下载相应数据。

图4为本发明一种利用车辆自组网络减少3G共享数据下载的方法之较佳 实施例的步骤流程图。以下将配合图4进一步说明步骤203，步骤203中每个阶 段的步骤如下：

3.1收集传输情况：包含每个车辆节点的缓存中需要传输的数据包的个数， 已经传输成功的数据包等信息。

3.2通过步骤0收集到的当前网络的传输情况以及车辆节点本地缓存信息， 更新待选种子节点的权重。

3.3将下载问题规划成最优化问题，目标是最小化通过3G下载的数据量， 约束是每个车辆节点要在时间约束前获取需要下载的数据，通过贪心算法求解该 最优化问题，得到近似最优解。

3.4利用车辆自组织网络的传输能力，使用两跳传输将数据在车辆网络中 传输。

步骤0中的优化问题为：

最小化：$\underset{u_i\in U}{\Sigma }\underset{p_k\in P}{\Sigma }{X}_i^{\left(k\right)}$

约束于：$\frac{\left|\right|W_{\mathrm{avg}}\left(k\right)\left(T\right)\left|\right|}{\left|\right|W_c\left|\right|}·\mathrm{Cos}\_\mathrm{Sim}(W_{\mathrm{avg}}\left(k\right)\left(T\right),W_c)\ge 1-\delta$

W_c＝{ε，ε，ε，...}

(1)将车辆网络中的车辆表示为一个集合V＝{v₁，v₂，v₃，...，v_n}，其中V的 一个子集合U＝{u₁，u₂，u₃，...，u_m}为需要下载数据包的车辆标识符，集合 P＝{p₁，p₂，...，p_k}代表需要下载的数据包。表示车辆u_i下载 数据p_k。向量$W^{\left(k\right)}\left(T\right){=}_{u_j\in U}(\underset{u_i\in S^{\left(k\right)}}{\Pi }{W}_{i1}^{\left(k\right)}T,...,\underset{u_i\in S^{\left(k\right)}}{\Pi }{W}_{\mathrm{ij}}^{\left(k\right)}T)$表示其中集合表示。针对 数据包p_k，选择已被经选为数据种子节点的车辆集合S^(k)，数据包p_k到达每个目 的节点的权重，其中$W_{\mathrm{avg}}^{\left(k\right)}\left(T\right)=\frac{1}{\left|P\right|}\underset{k\in P}{\Sigma }{W}^{\left(k\right)}\left(T\right).$表示针对所有需要下载的数据，待选 种子节点权重的平均值。

(2)权重向量W中的每一项w_ij^(k)(T)表示选取u_i为种子节点下载数据包pk 在数据时效T之前到达目的节点u_j的权重。

(3)向量W_c为常量向量，可通过改变ε的值来确定要达到的传输要求， ε一般为小于1且很小的数值。

(4)表示权重向量和约束向量的长度比，Cos_Sim(X，Y)表示 求解两个向量的余弦相似度。二者的乘积要大于1-δ，表示选择的种子节点的 权重向量要尽量接近约束常量向量，以达到传输要求。

编号0中，选择下载数据p_k的种子节点的权重函数为定义如下：

该等式表示选取u_i为种子节点下载数据包p_k在时 间T到达目的节点u_j失败的概率。其中表示u_i为种子节点下载数据包p_k通过中间中继节点v_r在时间T之前到达目的节点u_j的概率。之前的研究表明， 车辆之间的相邻两次相遇之间的间隔相遇时间服从指数分布。λ_ij是u_i和u_j间隔 相遇时间指数分布的率参数。因此可以得到从种子u_s节点，经过中继节点v_r两 跳到达目的节点u_d的概率为：

$P_{\mathrm{srd}}^{\left(k\right)}\left(T\right)=\frac{h_r^{\left(k\right)}{\lambda }_{\mathrm{rd}}}{h_r^{\left(k\right)}{\lambda }_{\mathrm{rd}}-g_s^{\left(k\right)}{\lambda }_{\mathrm{sr}}}(1-e^{-g_s^{\left(k\right)}{\lambda }_{\mathrm{sr}}T})+\frac{g_s^{\left(k\right)}{\lambda }_{\mathrm{sr}}}{g_s^{\left(k\right)}{\text{λ}}_{\mathrm{sr}}-h_r^{\left(k\right)}{\lambda }_{\mathrm{rd}}}(1-e^{-h_r^{\left(k\right)}{\lambda }_{\mathrm{rd}}T})$

其中分别为数据包p_k在单次相遇中能够被种子节点u_s和中继节点 v_r传输的平均概率，与车辆节点缓存中待传输的数据量有关，缓存信息可以通过 步骤3.1获取。

在每次决策阶段开始前，需根据前一阶段的传输情况和当前时刻的网络信 息更新待选种子节点的权重。解本优化问题可以使用贪心算法，得到近似最优 解。

综上所述，本发明一种利用车辆自组网络减少3G共享数据下载的方法及 系统基于车辆的历史相遇信息，通过选取最有利于车辆网络传输的种子节点， 充分利用车辆网络的传输能力将数据包传递给需要该数据包的目的节点，利用 车辆自组网络，达到既满足传输要求，又降低3G下载量的使用目的。

与现有技术相比，本发明具有以下优点：

1.通过低开销的车辆网络传输能力辅助高开销的3G网络下载，达到降低 使用者成本开销的目的。

2.使用多阶段决策思想，能够在多次决策中结合当前的传输情况，做出 更加准确的下载决定，减少3G使用的开销。

3.利用车辆历史的相遇信息，能够有效的制定下载策略，充分利用车辆 网络的传输能力。

上述实施例仅例示性说明本发明的原理及其功效，而非用于限制本发明。 任何本领域技术人员均可在不违背本发明的精神及范畴下，对上述实施例进行 修饰与改变。因此，本发明的权利保护范围，应如权利要求书所列。