基于云雾混合计算的车联网联合资源分配算法

唐伦; 肖娇; 魏延南; 赵国繁; 陈前斌

doi:10.11999/JEIT190306

基于云雾混合计算的车联网联合资源分配算法

doi: 10.11999/JEIT190306

1.
重庆邮电大学通信与信息工程学院重庆 400065
2.
重庆邮电大学移动通信技术重点实验室重庆 400065

基金项目: 国家自然科学基金(61571073)，重庆市教委科学技术研究项目(KJZD-M201800601)

详细信息

作者简介:
唐伦：男，1973年生，教授，博士生导师，主要研究方向为新一代无线通信网络、异构蜂窝网络等

肖娇：女，1995年生，硕士生，研究方向为蜂窝车联网络下的资源调度算法

魏延南：男，1995年生，硕士生，研究方向为5G网络切片、虚拟资源分配、随机优化理论

赵国繁：女，1993年生，硕士生，研究方向为5G网络切片中的资源分配，可靠性

陈前斌：男，1967年生，教授，博士生导师，主要研究方向为个人通信、多媒体信息处理与传输、下一代移动通信网络、异构蜂窝网络等

通讯作者:
肖娇　Ir_xiao@163.com

中图分类号: TN929.5
计量
- 文章访问数: 2114
- HTML全文浏览量: 750
- PDF下载量: 139
- 被引次数: 0
出版历程
- 收稿日期: 2019-04-30
- 修回日期: 2019-12-13
- 网络出版日期: 2020-07-01
- 刊出日期: 2020-08-18

Joint Resource Allocation Algorithms Based on Mixed Cloud/Fog Computing in Vehicular Network

1.
School of Communication and Information Engineering, Chongqing University of Post and Telecommunications, Chongqing 400065, China
2.
Key Laboratory of Mobile Communication Technology, Chongqing University of Post and Telecommunications, Chongqing 400065, China

Funds: The National Natural Science Foundation of China (61571073), The Science and Technology Research Program of Chongqing Municipal Education Commission (KJZD-M201800601)

摘要

摘要:
针对车联网业务的低时延、低功耗需求及海量设备计算卸载引起的网络拥塞问题，该文提出一种在云雾混合网络架构下的联合计算卸载、计算资源和无线资源分配算法(JODRAA)。首先，该算法考虑将云计算与雾计算结合，以最大时延作为约束，建立最小化系统能耗和资源成本的资源优化模型。其次，将原问题转化为标准二次约束二次规划(QCQP)问题，并设计一种低复杂度的联合卸载决策和计算资源分配算法。进一步，针对海量设备计算卸载引起的网络拥塞问题，建立卸载用户接入请求队列的上溢概率估计模型，提出一种基于在线测量的雾节点时频资源配置算法。最后，借助分式规划理论和拉格朗日对偶分解方法得到迭代的带宽和功率分配策略。仿真结果表明，该文算法可以在满足时延需求的前提下，最小化系统能耗和资源成本。
- 车联网 /
- 雾计算 /
- 计算卸载 /
- 资源分配
Abstract:
For the problems of low delay, low power requirement and access congestion caused by computational unloading of mass devices, a Joint Offloading Decision and Resource Allocation Algorithm (JODRAA) is proposed based on cloud-fog hybrid network architecture. Firstly, the algorithm considers the combination of cloud and fog computing, and establishes a resource optimization model to minimize system energy consumption and resource cost with maximum delay as constraint. Secondly, the original problem is transformed into a standard Quadratically Constrained Quadratic Program (QCQP) problem, and a low-complexity joint unloading decision-making and computational resource allocation algorithm is designed. Furthermore, considering the access congestion problem caused by massive computing of unloading devices, an estimation model of the overflow probability of unloading user access request queue is established, and an on-line measurement based time-frequency resource allocation algorithm for fog nodes is proposed. Finally, the iterative bandwidth and power allocation strategy is obtained by using fractional programming theory and Lagrange dual decomposition method. The simulation results show that the proposed algorithm can minimize the system energy consumption and resource cost on the premise of time delay.
- Vehicular network /
- Fog computing /
- Computation offload /
- Resource allocation

HTML全文

1. 引言

线性补对偶(Linear Complementary Dual, LCD)码是一类具有特殊结构的线性码，它由Massey^[1]引入并用于解决数据的有效存储。1992年，Massey^[2]证明LCD码为双用户加法器信道提供了一种最佳的线性编码方案。2014年，Bringer等人^[3]将2元LCD码用于抵抗侧信道攻击和错误注入攻击。2016年，Carlet和Guilley^[4]将 $q$ 元LCD码用于抵抗侧信道攻击和错误注入攻击，并给出了几种LCD码的构造方法。鉴于LCD码在抵御侧信道攻击和错误注入攻击方面的重要应用，LCD码的研究是一项重要的工作。2017年，Li等人^[5,6]构造了循环LCD码，并确定了它们的参数。2018年，Sok等人^[7]利用正交群、码的扩展和矩阵积码构造了大域上LCD码。2019年，Liu等人^[8]利用有限域上典型群构造了LCD码。2021年，Shi等人^[9]利用有限域上托普利兹矩阵构造了LCD码。最近，唐春明等人^[10]总结了有限域上LCD码的一些主要成果和进展，并提出了此研究领域的一些未解决的重要问题。与此同时，有限域上LCD极大距离可分(Linear Complementary Dual Maximum Distance Separable, LCD MDS)码的构造也得到了深入的研究。最近，金玲飞等人^[11]总结了有限域上LCD MDS码的一些主要成果和进展。除此之外，有限环上LCD码的构造也得到了深入的研究^[12-15]。

2018年，Carlet等人^[16]证明：给定参数为 $[n,k,d]$ 的 $q$ 元线性码，当 $q > 3$ 时，存在一个与其等价的具有相同参数的 $q$ 元LCD码。此后，2元和3元LCD码的构造受到重点关注。2017年，Rao等人^[17]利用循环码构造了一些参数好的2元LCD码。2018年，Seneviratne和Melcher^[18]利用几何的方法分别构造了一类2元和3元LCD码。2019年，Zhou等人^[19]利用定义集方法构造了参数优的2元LCD码。Carlet等人^[20]利用正交或辛基刻画了2元LCD码并研究了2元LCD码的最小距离。Galindo等人^[21]利用J-仿射变种码的子域子码，构造了参数好的2元和3元LCD码。Li等人^[22]利用定义集方法构造了参数优的3元LCD码。Liu等人^[23]确定了几类长度为 ${2^m} + 1$ 的2元线性补BCH(Linear Complementary Dual Bose Chaudhuri Hocquenghem, LCD BCH)码的参数。2020年，Wu等人^[24]利用单纯复形构造了参数优的2元LCD码。Huang等人^[25]构造了一类长度为 ${2^m} - 1$ 的LCD BCH码并研究了这类码的参数。Lu等人^[26]利用拓展、截断和组合等方法，构造了参数好的3元LCD码。2021年，Bouyuklieva^[27]研究了2元LCD码的性质及其最大极小重量的界。Araya等人^[28]给出了2元和3元LCD码的最大极小重量的一个刻画，并分类了小维数的最优2元和3元LCD码。Harada^[29]给出了2元和3元LCD码的两种构造方法，并改进了这两类LCD码的最大极小重量的界。Araya等人^[30]分别确定了维数为5的2元LCD码和维数为4的3元LCD码的最大极小重量。2022年，Liu等人^[31]利用矩阵积码，构造了渐近好的2元和3元LCD码。Huang等人^[32]确定了一些3元长度为 ${3^m} - 1$ 的LCD BCH码的重量分布。最近，李平等人^[33]利用定义集方法构造了一些参数优的3元LCD码。从研究现状分析，构造参数好的3元LCD码是一个有趣的问题。

本文利用环 ${\mathbb{F}_3} + u{\mathbb{F}_3}$ ( ${u^2} = 0$ )上循环码的Gray象构造3元LCD码。环 ${\mathbb{F}_3} + u{\mathbb{F}_3}$ 是一类有限链环。Dinh等人^[34]确定了有限链环上循环码的代数结构。Norton等人^[35]证明有限链环上线性码的Hamming距离等于其最高阶挠码的Hamming距离。张付丽等人^[36]确定了环 ${\mathbb{F}_q} + u{\mathbb{F}_q}$ 上循环码的剩余码和挠码的结构，并将其应用于构造量子码，其中 ${u^2} = 0$ 且 $q$ 是一个素数幂。本文通过引入 ${({\mathbb{F}_3} + u{\mathbb{F}_3})^n}$ 到 $\mathbb{F}_3^{2n}$ 的等距Gray映射，利用环 ${\mathbb{F}_3} + u{\mathbb{F}_3}$ 上长度为 $n$ 的循环码的Gray象，构造了几类长度为 $2n$ 的参数好的3元LCD码。

2. 预备知识

设 $R$ 是一个有限链环， ${R^n}$ 表示环 $R$ 上 $n$ -元组构成的 $R$ -模，其中 $n$ 为正整数。 ${R^n}$ 的每个非空子集 $C$ 称为环 $R$ 上长度为 $n$ 的码， $C$ 中每个 $n$ -元组称为码字。如果 $C$ 是 ${R^n}$ 的 $R$ -子模，则称 $C$ 是环 $R$ 上长度为 $n$ 的线性码。特别地，当 $R = {\mathbb{F}_3}$ 时，域 ${\mathbb{F}_3}$ 上线性码又称作3元线性码。设 ${\boldsymbol{x}} = ({x_0},{x_1}, \cdots ,{x_{n - 1}}) \in {R^n}$ 且

${\boldsymbol{y}} = ({y_0},{y_1}, \cdots ,{y_{n - 1}}) \in {R^n}$

(1)

${\boldsymbol{x}}$ 的Hamming重量定义为 ${\text{w}}{{\text{t}}_{\text{H}}}({\boldsymbol{x}}) = \left| \{ i|{x_i} \ne 0, 0 \le i \le n - 1\} \right|$ ， ${\boldsymbol{x}}$ 和 ${\boldsymbol{y}}$ 的Hamming距离定义为

${\text{dis}}{{\text{t}}_{\text{H}}}({\boldsymbol{x}},{\boldsymbol{b}}) = {\text{w}}{{\text{t}}_{\text{H}}}({\boldsymbol{x}} - {\boldsymbol{y}})$

(2)

码 $C$ 的Hamming距离定义为 $d(C) = \min \{ {\text{dis}}{{\text{t}}_{\text{H}}}({\boldsymbol{x}},{\boldsymbol{y}}) |{\boldsymbol{x}},{\boldsymbol{y}} \in C,{\boldsymbol{x}} \ne {\boldsymbol{y}}\}$ 。容易验证，当 $C$ 是环 $R$ 上长度为 $n$ 的线性码时， $d(C) = \min \{ {\text{w}}{{\text{t}}_{\text{H}}}({\boldsymbol{x}})|{\boldsymbol{x}} \in C,{\boldsymbol{x}} \ne {{ {\textit{0}}}}\}$ ，其中 ${ {\textit{0}}}$ 表示分量全为0的 $n$ -元组。环 $R$ 上长度为 $n$ 、Hamming距离为 $d$ 的线性码称作环 $R$ 上 $(n,M,d)$ 线性码，其中 $M$ 表示 $C$ 的势。特别地，当 $R = {\mathbb{F}_3}$ 时，域 ${\mathbb{F}_3}$ 上 $(n,M,d)$ 线性码又称作3元 $[n,k,d]$ 线性码，其中 $k = \dim (C) = {\log _3}M$ 。在 ${R^n}$ 上， $n$ -元组 ${\boldsymbol{x}}$ 和 ${\boldsymbol{y}}$ 的内积定义为 ${\boldsymbol{x}} \cdot {\boldsymbol{y}} = {x_0}{y_0} + {x_1}{y_1} + \cdots + {x_{n - 1}}{y_{n - 1}}$ 。码 $C$ 的对偶码定义为 ${C^ \bot } = \{ {\boldsymbol{x}} \in \mathbb{F}_3^n|{\boldsymbol{x}} \cdot {\boldsymbol{y}} = 0,\forall {\boldsymbol{y}} \in C\}$ 。如果 $C \cap {C^ \bot } = \{{ {\textit{0}}}\}$ ，则称 $C$ 是环 $R$ 上长度为 $n$ 的LCD码。

设 $C$ 是环 $R$ 上长度为 $n$ 的线性码，如果对任意 $({c_0},{c_1}, \cdots ,{c_{n - 1}}) \in C$ ，恒有 $({c_{n - 1}},{c_0}, \cdots ,{c_{n - 2}}) \in C$ ，则称 $C$ 是环 $R$ 上长度为 $n$ 的循环码。定义

$\begin{split} \psi :{R^n}& \mapsto \mathfrak{M} = {{R[x]} \mathord{\left/ {\vphantom {{R[x]} {({x^n} - 1)}}} \right. } {({x^n} - 1)}},({c_0},{c_1}, \cdots ,{c_{n - 1}}) \\ & \mapsto {c_0} + {c_1}x + \cdots + {c_{n - 1}}{x^{n - 1}} \end{split}$

(3)

且 $\psi (C) = \{ \psi ({\boldsymbol{c}})|{\boldsymbol{c}} \in C\}$ 。本文将 $C$ 等同于 $\psi (C)$ ，则 $C$ 是环 $R$ 上长度为 $n$ 的循环码当且仅当 $C$ 是商环 $\mathfrak{M}$ 的理想。当 $R = {\mathbb{F}_3}$ 时，商环 $\mathfrak{M}$ 是一个主理想环。因此，存在 ${x^n} - 1$ 的首一因子 $g(x)$ 使得 $C = (g(x))$ ，并且码 $C$ 的维数 $k = n - \deg (g(x))$ ，其中 $\deg (g(x))$ 表示多项式 $g(x)$ 的次数。设 $f(x) = {f_0} + {f_1}x + \cdots + {f_t}{x^t} \in {\mathbb{F}_3}[x]$ ，其中 ${f_0}{f_t} \ne 0$ ， $f(x)$ 的互反多项式定义为 ${f^*}(x) = f_0^{ - 1} \cdot {x^{\deg (f(x))}} \cdot f({x^{ - 1}})$ 。文献[1]给出了有限域上循环码是LCD码的充要条件。

引理1^[1]　设 $C = (g(x))$ 是长度为 $n$ 的3元循环码，其中 $g(x)|({x^n} - 1)$ ，则 $C$ 是LCD码当且仅当 ${g^*}(x) = g(x)$ 。

当 $R = {\mathbb{F}_3} + u{\mathbb{F}_3}$ 时，其中 ${u^2} = 0$ 。易知 $R$ 是一个以 $(u)$ 为极大理想，剩余域为 ${\mathbb{F}_3}$ 的有限链环。对于环 $R$ 上长度为 $n$ 的线性码 $C$ ，存在两个与其相关的3元码：剩余码 ${\text{Res}}(C) = \{ {\boldsymbol{x}} \in \mathbb{F}_3^n|\exists {\boldsymbol{y}} \in \mathbb{F}_3^n,{\boldsymbol{x}} + u{\boldsymbol{y}} \in C\}$ 和挠码 ${\text{Tor}}(C) = \{ {\boldsymbol{x}} \in \mathbb{F}_3^n|u{\boldsymbol{x}} \in C\}$ 。由文献[35]，剩余码 ${\text{Res}}(C)$ 和挠码 ${\text{Tor}}(C)$ 都是长度为 $n$ 的3元线性码且 $\left| C \right| = \left| {{\text{Res}}(C)} \right| \cdot \left| {{\text{Tor}}(C)} \right|$ 。通常，商环 $\mathfrak{M}$ 不是一个主理想环，因此环 $R$ 上长度为 $n$ 的循环码的代数结构较为复杂。当 $n$ 与剩余域的特征互素时，文献[34]确定了有限链环上循环码的代数结构。将相关结果应用到环 $R$ 上循环码，有如下结论。

引理2^[34]　设 $n$ 是一个正整数且 $\gcd (n,3) = 1$ 。设 $C$ 是环 ${\mathbb{F}_3} + u{\mathbb{F}_3}$ 上长度为 $n$ 的循环码，则存在唯一的首一多项式 $f(x)$ 和 $h(x)$ 使得 $C = (f(x)h(x),uf(x))$ ，其中 $f(x)h(x)|({x^n} - 1)$ 。

文献[36]研究了环 ${\mathbb{F}_q} + u{\mathbb{F}_q}$ 上循环码的挠码，其中 ${u^2} = 0$ 且 $q$ 是一个素数幂。将相关结果应用到 ${\mathbb{F}_3} + u{\mathbb{F}_3}$ 上循环码，有如下结论。

引理3^[36]　设 $n$ 是一个正整数且 $\gcd (n,3) = 1$ 。设 $C = (f(x)h(x),uf(x))$ 是环 ${\mathbb{F}_3} + u{\mathbb{F}_3}$ 上长度为 $n$ 的循环码，其中 $f(x)$ 和 $h(x)$ 是 ${\mathbb{F}_3}$ 上首一多项式且 $f(x)\,h(x)|({x^n} \,-\, 1)$ 。则 ${\text{Res}}(C) \;=\; (f(x)\,h(x))$ 且 ${\text{Tor}}(C) = (f(x))$ 。

3. 3元LCD码的构造

下文约定 $n$ 是与3互素的正整数且 $R = {\mathbb{F}_3} + u{\mathbb{F}_3}$ ，其中 ${u^2} = 0$ 。首先引入环 $R$ 到 $\mathbb{F}_3^2$ 的Gray映射。

设 $r \in R$ ，则 $r = x + uy$ ，其中 $x,y \in {\mathbb{F}_3}$ 。定义 $R$ 到 $\mathbb{F}_3^2$ 的Gray映射 $\phi$ 为 $\phi (r) = (y + x,y - x)$ 。元素 $r$ 的Gray重量定义为

${\text{wt}}_{\text{G}}(r)=\left\{\begin{aligned} & 0,\;x=y=0\\ & 1,\;xy\ne 0\\ & 2,\;其他\end{aligned} \right.$

(4)

映射 $\phi$ 可以按照自然的方式拓展到 ${R^n}$ 至 $\mathbb{F}_3^{2n}$ 上，即

$\begin{split} \phi :{R^n} & \to \mathbb{F}_3^{2n},({x_0},{x_1}, \cdots ,{x_{n - 1}})\\ & \mapsto (\phi ({x_0}),\phi ({x_1}), \cdots ,\phi ({x_{n - 1}})) \end{split}$

(5)

$n$ 元组 ${\boldsymbol{x}} = ({x_0},{x_1}, \cdots ,{x_{n - 1}}) \in {R^n}$ 的Gray重量定义为

${\text{w}}{{\text{t}}_{\text{G}}}({\boldsymbol{x}}) = {\text{w}}{{\text{t}}_{\text{G}}}({x_0}) + {\text{w}}{{\text{t}}_{\text{G}}}({x_1}) + \cdots + {\text{w}}{{\text{t}}_{\text{G}}}({x_{n - 1}})$

(6)

两个 $n$ 元组 ${\boldsymbol{x}}$ 和 ${\boldsymbol{y}}$ 的Gray距离定义为 ${\text{dis}}{{\text{t}}_{\text{G}}}({\boldsymbol{x}},{\boldsymbol{y}}) = {\text{w}}{{\text{t}}_{\text{G}}}({\boldsymbol{x}} - {\boldsymbol{y}})$ 。

设 $C$ 是环 $R$ 上长度为 $n$ 的码， $C$ 的Gray距离定义为

${d_{\text{G}}}(C) = \min \{ {\text{dis}}{{\text{t}}_{\text{G}}}({\boldsymbol{x}},{\boldsymbol{y}})|{\boldsymbol{x}},{\boldsymbol{y}} \in C,{\boldsymbol{x}} \ne {\boldsymbol{y}}\}$

(7)

容易验证，当 $C$ 是线性码时， ${d_{\text{G}}}(C) = \min \{ {\text{w}}{{\text{t}}_{\text{G}}}({\boldsymbol{x}})| {\boldsymbol{x}} \in C,{\boldsymbol{x}} \ne { {\textit{0}}}\}$ 。环 $R$ 上长度为 $n$ 、Gray距离为 ${d_{\text{G}}}$ 的线性码称作环 $R$ 上 $(n,M,{d_{\text{G}}})$ 线性码，其中 $M$ 表示 $C$ 的势。

环 $R$ 上长度为 $n$ 的码 $C$ 的Gray象定义为 $\phi (C) = \{ \phi ({\boldsymbol{c}})|{\boldsymbol{c}} \in C\}$ 。下面给出环 $R$ 上线性码的Gray象的结构性质。

定理1　设 $C$ 是环 $R$ 上 $(n,M,{d_{\text{G}}})$ 线性码，则

(1) $\phi (C)$ 是3元 $[2n,k,{d_{\text{G}}}]$ 线性码，其中 $k = {\log _3}M$ 。

(2) 如果 ${\text{Res}}(C) \subseteq C$ 且 ${\text{Res}}(C) \cap {\text{Res}}{(C)^ \bot } = {\text{Tor}}(C) \cap {\text{Tor}}{(C)^ \bot } = \{ {{ {\textit{0}}}}\}$ ，其中 ${{ {\textit{0}}}}$ 表示长度为 $n$ 的0向量。则 $\phi (C)$ 是长度为 $2n$ 的3元LCD码。

证明　(1) 容易验证，对任意的 $a,b \in {\mathbb{F}_3}, {\boldsymbol{x}},{\boldsymbol{y}} \in {R^n}$ , $\phi (a{\boldsymbol{x}} + b{\boldsymbol{y}}) = a\phi ({\boldsymbol{x}}) + b\phi ({\boldsymbol{y}})$ 。因此， $\phi (C)$ 是一个长度为 $2n$ 的3元线性码。由Gray映射的定义，对任意 ${\boldsymbol{x}},{\boldsymbol{y}} \in {R^n}$

$\begin{split} {\text{dis}}{{\text{t}}_{\text{G}}}({\boldsymbol{x}},{\boldsymbol{y}}) =& {\text{w}}{{\text{t}}_{\text{G}}}({\boldsymbol{x}} - {\boldsymbol{y}}) = {\text{w}}{{\text{t}}_{\text{H}}}(\phi ({\boldsymbol{x}} - {\boldsymbol{y}})) \\ =& {\text{w}}{{\text{t}}_{\text{H}}}(\phi ({\boldsymbol{x}}) - \phi ({\boldsymbol{y}})) = {\text{dis}}{{\text{t}}_{\text{H}}}(\phi ({\boldsymbol{x}}),\phi ({\boldsymbol{y}})) \end{split}$

(8)

因此， $\phi (C)$ 的Hamming距离为 ${d_{\text{G}}}$ 。又因为 $\phi$ 是一个双射，故 $\phi (C)$ 是一个3元 $[2n,k,{d_{\text{G}}}]$ 线性码。

(2) 设 ${\boldsymbol{x}} + u{\boldsymbol{y}} \in C$ ，其中 ${\boldsymbol{x}},{\boldsymbol{y}} \in \mathbb{F}_3^n$ 。由剩余码 ${\text{Res}}(C)$ 的定义， ${\boldsymbol{x}} \in {\text{Res}}(C)$ 。因为 ${\text{Res}}(C) \subseteq C$ ，所以 ${\boldsymbol{x}} \in C$ 。由此推出， $u{\boldsymbol{y}} \in C$ ，故 ${\boldsymbol{y}} \in {\text{Tor}}(C)$ 。因此，码 $C$ 的任意一个码字都可以表示为 ${\boldsymbol{x}} + u{\boldsymbol{y}}$ ，其中 ${\boldsymbol{x}} \in {\text{Res}}(C)$ , ${\boldsymbol{y}} \in {\text{Tor}}(C)$ 。

设 $\phi ({\boldsymbol{x}} + u{\boldsymbol{y}}) \in \phi (C) \cap \phi {(C)^ \bot }$ ，其中 ${\boldsymbol{x}} = ({x_0},{x_1}, \cdots ,{x_{n - 1}}) \in \mathbb{F}_3^n$ 且 ${\boldsymbol{y}} = ({y_0},{y_1}, \cdots ,{y_{n - 1}}) \in \mathbb{F}_3^n$ 。一方面，设

${\boldsymbol{a}} = ({a_0},{a_1}, \cdots ,{a_{n - 1}}) \in \mathbb{F}_3^n$

(9)

是 ${\text{Res}}(C)$ 的任意一个码字，则 $\phi ({\boldsymbol{a}}) \in \phi (C)$ 。因为 $\phi ({\boldsymbol{x}} + u{\boldsymbol{y}}) \in \phi {(C)^ \bot }$ ，所以

$\begin{split} \phi ({\boldsymbol{x}} + u{\boldsymbol{y}}) \cdot \phi ({\boldsymbol{a}}) =& \sum\limits_{i = 0}^{n - 1} {[({y_i} + {x_i}){a_i} + ({y_i} - {x_i})( - {a_i})]} \\ =& 2\sum\limits_{i = 0}^{n - 1} {{x_i}{a_i}} = 0 \\[-21pt] \end{split}$

(10)

即 $\displaystyle\sum\nolimits_{i = 0}^{n - 1} {{x_i}{a_i}} = 0$ 。由此推出， ${\boldsymbol{x}} \in {\text{Res}}(C) \cap {\text{Res}}{(C)^ \bot }$ ，故 ${\boldsymbol{x}} = {0}$ 。另一方面，设

${\boldsymbol{b}} = ({b_0},{b_1}, \cdots ,{b_{n - 1}}) \in \mathbb{F}_3^n$

(11)

是 ${\text{Tor}}(C)$ 的任意一个码字，则 $\phi (u{\boldsymbol{b}}) \in \phi (C)$ 。由 $\phi ({\boldsymbol{x}} + u{\boldsymbol{y}}) \in \phi {(C)^ \bot }$ 推出

$\begin{split} \phi ({\boldsymbol{x}} + u{\boldsymbol{y}}) \cdot \phi (u{\boldsymbol{b}}) =& \sum\limits_{i = 0}^{n - 1} {[({y_i} + {x_i}){b_i} + ({y_i} - {x_i}){b_i}]} \\ =& 2\sum\limits_{i = 0}^{n - 1} {{y_i}{b_i}} = 0 \\[-21pt] \end{split}$

(12)

即 $\displaystyle\sum\nolimits_{i = 0}^{n - 1} {{y_i}{b_i}} = 0$ 。由此推出， ${\boldsymbol{y}} \in {\text{Tor}}(C) \cap {\text{Tor}}{(C)^ \bot }$ ，即 ${\boldsymbol{y}} = {{ {\textit{0}}}}$ 。综上所述， $\phi (C) \cap \phi {(C)^ \bot } = \{ {\bar { {\textit{0}}}}\}$ ，其中 ${\bar { {\textit{0}}}}$ 表示长度为 $2n$ 的0向量。证毕

下面利用环 $R$ 上循环码的Gray象构造3元LCD码。为此给出两个重要的引理。

引理4　设 $C = (f(x)h(x),uf(x))$ 是环 $R$ 上长度为 $n$ 的循环码，其中 $f(x)$ 和 $h(x)$ 是 ${\mathbb{F}_3}$ 上首一多项式且 $f(x)h(x)|({x^n} - 1)$ 。则 ${\text{Res}}(C) \subseteq C$ 且 ${\text{Res}}(C) \cap {\text{Res}}{(C)^ \bot } = {\text{Tor}}(C) \cap {\text{Tor}}{(C)^ \bot } = \{ {{ {\textit{0}}}}\}$ 当且仅当 ${f^*}(x) = f(x)$ 且 ${h^*}(x) = h(x)$ 。

证明　由引理3， ${\text{Res}}(C) = (f(x)h(x))$ 。因为 $f(x)h(x) \in C$ ，所以 ${\text{Res}}(C) \subseteq C$ 。一方面，由引理1， ${\text{Res}}(C) \cap {\text{Res}}{(C)^ \bot } = \{ { {\textit{0}}}\}$ 当且仅当 ${(f(x)h(x))^*} = f(x)h(x)$ 。容易验证， ${(f(x)h(x))^*} = {f^*}(x){h^*}(x)$ 。因此， ${(f(x)h(x))^*} = f(x)h(x)$ 等价于 ${f^*}(x){h^*}(x) = f(x)h(x)$ 。另一方面，由引理3， ${\text{Tor}}(C) = (f(x))$ 。由引理1， ${\text{Tor}}(C) \cap {\text{Tor}}{(C)^ \bot } = \{ {{ {\textit{0}}}}\}$ 当且仅当 ${f^*}(x) = f(x)$ 。综合两方面，结论成立。证毕

引理5　设 $C = (f(x)h(x),uf(x))$ 是环 $R$ 上长度为 $n$ 的循环码，其中 $f(x)$ 和 $h(x)$ 是 ${\mathbb{F}_3}$ 上首一多项式且 $f(x)h(x)|({x^n} - 1)$ 。则 $C$ 的Gray距离 ${d_{\text{G}}}$ 满足： $\min \{ {d_1},2{d_2}\} \le {d_{\text{G}}} \le 2{d_2}$ ，其中 ${d_1}$ 和 ${d_2}$ 分别是 ${\text{Res}}(C)$ 和 ${\text{Tor(}}C)$ 的Hamming距离。

证明　设 $c(x) = a(x) + ub(x) \in C$ 且 $c(x) \ne 0$ 。由引理4， ${\text{Res}}(C) \subseteq C$ ，所以 $a(x) \in {\text{Res}}(C)$ 且 $b(x) \in {\text{Tor}}(C)$ 。由Gray重量的定义

$\begin{split} {\text{w}}{{\text{t}}_{\text{G}}}(c(x)) =& {\text{w}}{{\text{t}}_{\text{H}}}((b(x) + a(x)|b(x) - a(x))) \\ = &{\text{w}}{{\text{t}}_{\text{H}}}(b(x) + a(x)) + {\text{w}}{{\text{t}}_{\text{H}}}(b(x) - a(x)) \end{split}$

(13)

其中， $( - | - )$ 表示向量的级联。当 $a(x) = 0$ 时， $b(x) \ne 0$ 且 ${\text{w}}{{\text{t}}_{\text{G}}}(c(x)) = 2 \cdot {\text{w}}{{\text{t}}_{\text{H}}}(b(x))$ 。由于 $b(x) \in {\text{Tor}}(C)$ ，所以 ${\text{w}}{{\text{t}}_{\text{G}}}(c(x)) \ge 2{d_2}$ 。当 $a(x) \ne 0$ 时，注意到

${\text{w}}{{\text{t}}_{\text{G}}}(c(x)) \ge {\text{max\{ w}}{{\text{t}}_{\text{H}}}(a(x)),{\text{w}}{{\text{t}}_{\text{H}}}(b(x))\} \ge {d_1}$

(14)

因此， ${\text{w}}{{\text{t}}_{\text{G}}}(c(x)) \ge \min \{ {d_1},2{d_2}\}$ ，即 ${d_{\text{G}}} \ge \min \{ {d_1},2{d_2}\}$ 。特别地，因为 ${\text{Tor(}}C)$ 的Hamming距离为 ${d_2}$ ，所以存在 $\lambda (x) \in {\text{Tor}}(C)$ 使得 ${\text{w}}{{\text{t}}_{\text{H}}}(\lambda (x)) = {d_2}$ 。注意到 $u\lambda (x) \in C$ 且 ${\text{w}}{{\text{t}}_{\text{G}}}(u\lambda (x)) = 2{d_2}$ ，因此， ${d_{\text{G}}} \le 2{d_2}$ 。证毕

由引理4和引理5，利用环 $R$ 上循环码可以构造如下参数的3元LCD码。

定理2　设 $f(x)$ 和 $h(x)$ 是 ${\mathbb{F}_3}$ 上首一多项式且使得 $f(x)h(x)|({x^n} - 1)$ , ${f^*}(x) = f(x)$ 且 ${h^*}(x) = h(x)$ 。设 ${d_1}$ 和 ${d_2}$ 分别是长度为 $n$ 的3元循环码 $(f(x)h(x))$ 和 $(f(x))$ 的Hamming距离。设 $C = (f(x)h(x),uf(x))$ 是环 $R$ 上长度为 $n$ 的循环码，则 $\phi (C)$ 是3元 $[2n,2n - 2\deg (f(x)) - \deg (h(x)),d]$ LCD码，其中 $\min \{ {d_1},2{d_2}\} \le d \le 2{d_2}$ 。

证明　由引理3， ${\text{Res}}(C) = (f(x)h(x))$ 且 ${\text{Tor}}(C) = (f(x))$ 。当 ${f^*}(x) = f(x)$ 且 ${h^*}(x) = h(x)$ 时，由引理4， ${\text{Res}}(C) \subseteq C$ 且 ${\text{Res}}(C) \cap {\text{Res}}{(C)^ \bot } = {\text{Tor}}(C) \cap {\text{Tor}}{(C)^ \bot } = \{ {{ {\textit{0}}}}\}$ 。由定理1， $\phi (C)$ 是长度为 $2n$ 的LCD码。码 $\phi (C)$ 的维数

$\begin{split} k =& {\log _3}\left| C \right| = {\log _3}(\left| {{\text{Res}}(C)} \right| \cdot \left| {{\text{Tor}}(C)} \right|) \\ =& \dim ({\text{Res}}(C)) + \dim ({\text{Tor}}(C)) \\ =& n - \deg (f(x)h(x)) + n - \deg (f(x)) \\ =& 2n - 2\deg (f(x)) - \deg (h(x)) \end{split}$

(15)

由引理5，码 $C$ 的Gray距离 ${d_{\rm{G}}}$ 满足 $\min \{ {d_1},2{d_2}\} \le {d_{\text{G}}} \le 2{d_2}$ 。由定理1，码 $\phi (C)$ 的Hamming距离 $d = {d_{\text{G}}}$ 。综上所述，结论成立。证毕

下面利用定理2，构造4类参数好的3元LCD码。为此引入以下术语：设 $\beta$ 是一个 $n$ 次本原单位根， $\beta$ 在 ${\mathbb{F}_3}$ 上的极小多项式 $M(x)$ 是以 $\beta$ 为零点次数最低的首一多项式。 $3$ 模 $n$ 的阶 ${\text{or}}{{\text{d}}_n}(3)$ 定义为使得 ${3^m} \equiv 1(\bmod n)$ 的最小正整数 $m$ 。设 ${\text{or}}{{\text{d}}_n}(3) = e$ ，则 $M(x) = \prod\nolimits_{j = 0}^{e - 1} {(x - {\beta ^{{3^j}}})}$ 且 $\deg (M(x)) = e$ 。由互反多项式的定义， ${M^*}(x) = \prod\nolimits_{j = 0}^{e - 1} {(x - {\beta ^{ - {3^j}}})}$ 。因此， ${M^*}(x) = M(x)$ 当且仅当存在 $0 \le j \le e - 1$ 使得 ${3^j} \equiv - 1(\bmod n)$ 。

定理3　设 $n$ 是一个正整数且存在 $j$ 使得 ${3^j} \equiv - 1(\bmod n)$ 。设 $m$ 是使得 ${3^m} \equiv - 1(\bmod n)$ 的最小正整数。设 $\beta$ 是一个 $n$ 次本原单位根且 $M(x)$ 是 $\beta$ 在 ${\mathbb{F}_3}$ 上的极小多项式。设 $C = ((x - 1)M(x), u(x - 1))$ 是环 $R$ 上长度为 $n$ 的循环码，则 $\phi (C)$ 是3元 $[2n,2n - 2m - 2,4]$ LCD码，且 ${\text{Res}}(C)$ 是3元 $[n,n - 2m - 1, d \ge 4]$ LCD码。

证明　显然， ${(x - 1)^*} = x - 1$ 。因为存在 $j$ 使得 ${3^j} \equiv - 1(\bmod n)$ ，所以 ${M^*}(x) = M(x)$ 。又因为 $m$ 是使得 ${3^m} \equiv - 1(\bmod n)$ 的最小正整数，所以 ${\text{or}}{{\text{d}}_n}(3) = 2m$ ，即 $\deg (M(x)) = 2m$ 。由定理2， $\phi (C)$ 是一个3元 $[2n,2n - 2m - 2]$ LCD码。由引理3， ${\text{Res}}(C) = ((x - 1)M(x))$ ，则 ${\text{Res}}(C)$ 是3元 $[n,n - 2m - 1]$ LCD码。下面讨论 $\phi (C)$ 和 ${\text{Res}}(C)$ 的Hamming距离。

显然， ${\text{Tor}}(C) = (x - 1)$ 的Hamming距离 ${d_2} = 2$ 。设 ${d_1}$ 是 ${\text{Res}}(C)$ 的Hamming距离。注意到 ${3^m} \equiv - 1(\bmod n)$ ，即 ${\beta ^{ - 1}}$ 是 $M(x)$ 的零点。进而， ${\beta ^{ - 1}}, {\beta ^0},\beta$ 是 $(x - 1)M(x)$ 的零点。由BCH界^[37]， ${d_1} \ge 4$ 。综合两方面，由定理2， $\phi (C)$ 的Hamming距离 $d = 4$ 。证毕

由定理3，可以得到如下两类具体的LCD码。

推论1　设 $n = {3^m} + 1$ ，其中 $m$ 为整数。设 $\beta$ 是一个 $n$ 次本原单位根且 $M(x)$ 是 $\beta$ 在 ${\mathbb{F}_3}$ 上的极小多项式。设 $C = ((x - 1)M(x),u(x - 1))$ 是环 $R$ 上长度为 $n$ 的循环码，则 $\phi (C)$ 是3元 $[2 \cdot {3^m} + 2,2 \cdot {3^m} - 2m,4]$ LCD码，且剩余码 ${\text{Res}}(C) = ((x - 1)M(x))$ 是3元 $[{3^m} + 1,{3^m} - 2m,d \ge 4]$ LCD码。

下面分析定理3构造的LCD码的性能。当 $[n,k,d]$ LCD码用于抵御侧信道攻击时，零偏移遮蔽对策是 $d - 1$ 阶安全的。当 $[n,k,d]$ LCD码用于抵御错误注入攻击时，任何一个Hamming重量严格小于 $d$ 的错误都可以被检测出来。因此，对固定的长度 $n$ 和维数 $k$ ，构造Hamming距离尽可能大的LCD码是一个重要的问题。对于 $[n,k,d]$ 线性码，存在如下两个重要的界：

(1) Hamming界^[37]： $\displaystyle\sum\limits_{i = 0}^{\left\lfloor {(d - 1)/2} \right\rfloor } {\left( {\begin{array}{*{20}{c}} n \\ i \end{array}} \right){2^i}} \le {3^{n - k}}$ ，其中 $\left\lfloor x \right\rfloor$ 表示不超过 $x$ 的最大整数。

(2) 当 $n \ge 2$ 且 $d$ 是偶数时^[38]， $\displaystyle\sum\limits_{i = 0}^{(d - 2)/2} {\left( {\begin{array}{*{20}{c}} {n - 1} \\ i \end{array}} \right){2^i}} \le {3^{n - 1 - k}}$ 。

当 $n = {3^m} + 1$ 时，由Hamming界，长度为 $n$ 、维数为 $n - 2m - 1$ 的3元线性码的Hamming距离 $d \le 6$ 。由界(2)，不存在3元 $[n,n - 2m - 1,6]$ 线性码。因此，根据线性码的理论界，长度为 $n$ 、维数为 $n - 2m - 1$ 的3元线性码的Hamming距离 $d \le 5$ 。同理，由线性码的理论界，当 $n = 2({3^m} + 1)$ 时，长度为 $n$ 、维数为 $n - 2m - 2$ 的3元线性码的Hamming距离 $d \le 5$ 。因此，推论1构造的两类LCD码的Hamming距离与理论界相差1，具有较好的参数。一方面，与线性码的理论界比较，定理3可以构造参数较好的LCD码。另一方面，与码表^[39]比较，定理3可以构造已知参数最好的LCD码。下面给出几个具体的例子加以说明。

例1　设 $\beta \in {\mathbb{F}_{{3^2}}}$ 是 ${x^2} + 1$ 的一个零点，则 $\beta$ 是一个4次本原单位根。设 $C = ((x - 1)({x^2} + 1),u(x - 1))$ 是环 $R$ 上长度为4的循环码。由推论1， $\phi (C)$ 是3元[8,4,4]LCD码。一方面，不存在3元 $[8,4,d \ge 5]$ 线性码，因此， $\phi (C)$ 的Hamming距离达到了最大值。另一方面，不存在3元 $[8,k \ge 5,4]$ 线性码，因此， $\phi (C)$ 的维数达到了最大值。同时，不存在3元 $[n \le 7,4,4]$ 线性码，因此， $\phi (C)$ 的长度达到了最小值。综合3方面， $\phi (C)$ 是最优的3元LCD码。

例2　设 $\beta \in {\mathbb{F}_{{3^4}}}$ 是 ${x^4} + 2{x^3} + {x^2} + 2x + 1$ 的一个零点，则 $\beta$ 是一个 $10$ 次本原单位根。设

$C = ((x - 1)({x^4} + 2{x^3} + {x^2} + 2x + 1),u(x - 1))$

(16)

是环 $R$ 上长度为 $10$ 的循环码。由推论1， $\phi (C)$ 是3元[20,14,4]LCD码，且 ${\text{Res}}(C)$ 是3元[10,5,4] LCD码。因为不存在3元 $[20,14,d \ge 5]$ 线性码， $\phi (C)$ 的Hamming距离达到了最大值，所以 $\phi (C)$ 是最优的3元LCD码。由码表^[39]，长度为 $10$ 维数为 $5$ 的3元线性码的Hamming距离的最大值为 $5$ 。因此， ${\text{Res}}(C)$ 是几乎最优的3元LCD码。

例3　设 $\beta \in {\mathbb{F}_{{3^6}}}$ 是 ${x^6} + 2{x^5} + 2{x^3} + 2x + 1$ 的一个零点，则 $\beta$ 是一个 $28$ 次本原单位根。设

$C = ((x - 1)({x^6} + 2{x^5} + 2{x^3} + 2x + 1),u(x - 1))$

(17)

是环 $R$ 上长度为 $28$ 的循环码。由推论1， $\phi (C)$ 是3元 $[56,48,4]$ LCD码，且 ${\text{Res}}(C)$ 是3元[28,21,4] LCD码。根据理论界，长度为 $56$ 维数为 $48$ 的3元线性码的Hamming距离 $d \le 5$ 。由码表^[39]，长度为 $56$ 维数为 $48$ 的3元线性码的Hamming距离的已知最大值为 $4$ 。因此， $\phi (C)$ 是已知参数最好的3元LCD码。同理，由码表^[39]，长度为 $28$ 维数为 $21$ 的3元线性码的Hamming距离的已知最大值为 $4$ 。因此， ${\text{Res}}(C)$ 也是已知参数最好的3元LCD码。

定理4　设 $n$ 是 ${3^m} - 1$ 的正因子且 $n > {3^{m/2}} + 1$ ，其中 $m \ge 2$ 为正整数。设 $\beta$ 是一个 $n$ 次本原单位根且 $M(x)$ 是 $\beta$ 在 ${\mathbb{F}_3}$ 上的极小多项式。设 $C = ((x - 1)M(x) {M^*}(x), u(x - 1))$ 是环 $R$ 上长度为 $n$ 的循环码，则 $\phi (C)$ 是3元 $[2n,2n - 2m - 2,4]$ LCD码，且 ${\text{Res}}(C)$ 是3元 $[n,n - 2m - 1,d \ge 4]$ LCD码。

证明　设 ${\text{or}}{{\text{d}}_n}(3) = e$ 。因为 $n$ 整除 ${3^m} - 1$ ，所以 $e$ 整除 $m$ 。当 $e < m$ 时

$0 < {3^e} - 1 \le {3^{m/2}} - 1 < n$

(18)

这与 $n$ 整除 ${3^e} - 1$ 矛盾。因此， $\deg (M(x)) = \deg ({M^*}(x)) = m$ 。下面证明 $M(x) \ne {M^*}(x)$ 。假设 $M(x) = {M^*}(x)$ ，则 ${\beta ^{ - 1}}$ 是 $M(x)$ 的零点，其等价于存在 $0 \le j \le m - 1$ 使得 $- 1 \equiv {3^j}(\bmod n)$ 。当 $0 \le j \le m/2$ 时， $0 < {3^j} + 1 \le {3^{m/2}} + 1 < n$ ，矛盾。当 $m/2 + 1 \le j \le m - 1$ 时， $- 1 \equiv {3^j}(\bmod n)$ 与 $- {3^{m - j}} \equiv {3^m} \equiv 1(\bmod n)$ 等价。同理， $0 < {3^{m - j}} + 1 \le {3^{m/2 - 1}} + 1 < n$ ，矛盾。因此， ${\text{Res}}(C) = ((x - 1)M(x){M^*}(x))$ 且 ${\text{Tor}}(C) = (x - 1)$ 。与定理3类似可证， ${\text{Tor}}(C)$ 的Hamming距离 ${d_2} = 2$ ， ${\text{Res}}(C)$ 的Hamming距离 ${d_1} \ge 4$ 。由定理2， $\phi (C)$ 是3元 $[2n,2n - 2m - 2,4]$ LCD码。由引理1， ${\text{Res}}(C)$ 是3元 $[n,n - 2m - 1,d \ge 4]$ LCD码。证毕

由定理4，可以得到如下两类具体的LCD码。

推论2　设 $n = {3^m} - 1$ ，其中 $m \ge 2$ 为正整数。设 $\beta$ 是一个 $n$ 次本原单位根且 $M(x)$ 是 $\beta$ 在 ${\mathbb{F}_3}$ 上的极小多项式。设 $C = ((x - 1)M(x),u(x - 1))$ 是环 $R$ 上长度为 $n$ 的循环码，则 $\phi (C)$ 是3元 $[2 \cdot {3^m} - 2,2 \cdot {3^m} - 2m - 4,4]$ LCD码，且 ${\text{Res}}(C)$ 是3元 $[{3^m} - 1,{3^m} - 2m - 2, d \ge 4]$ LCD码。

下面分析定理4构造的LCD码的性能。基于以上分析，对于抵御侧信道攻击和错误注入攻击，对固定的长度 $n$ 和维数 $k$ ，构造Hamming距离尽可能大的LCD码是一个重要的问题。当 $n = {3^m} - 1$ 时，由Hamming界，长度为 $n$ 、维数为 $n - 2m - 1$ 的3元线性码的Hamming距离 $d \le 6$ 。由界(2)，不存在3元 $[n,n - 2m - 1,6]$ 线性码。因此，根据线性码的理论界，长度为 $n$ 、维数为 $n - 2m - 1$ 的3元线性码的Hamming距离 $d \le 5$ 。同理，根据线性码的理论界，当 $n = 2({3^m} - 1)$ 时，长度为 $n$ 、维数为 $n - 2m - 2$ 的3元线性码的Hamming距离 $d \le 5$ 。因此，推论2构造的两类3元LCD码的Hamming距离与理论界相差1，具有较好的参数。一方面，与线性码的理论界比较，定理4可以构造参数好的LCD码。另一方面，与码表^[39]比较，定理4可以构造已知参数最好的LCD码。下面给出两个具体的例子加以说明。

例4　设 $\beta \in {\mathbb{F}_{{3^2}}}$ 是 ${x^2} + 2x + 2$ 的一个零点，则 $\beta$ 是 $8$ 次本原单位根。显然， ${({x^2} + 2x + 2)^*} = {x^2} + x + 2$ 。设 $C = ((x - 1)({x^2} + 2x + 2)({x^2} + x + 2),u(x - 1))$ 是环 $R$ 上长度为 $8$ 的循环码。由推论2， $\phi (C)$ 是3元[16,10,4] LCD码，且 ${\text{Res}}(C)$ 是3元 [8,3,4] LCD码。由码表^[39]，不存在3元 $[16,10,d \ge 5]$ 线性码，因此 $\phi (C)$ 是最优的3元LCD码。同理，由码表^[39]，长度为8维数为3的3元线性码的Hamming距离的最大值为5。因此， ${\text{Res}}(C)$ 是几乎最优的3元LCD码。

例5　设 $\beta \in {\mathbb{F}_{{3^3}}}$ 是 ${x^3} + 2x + 1$ 的一个零点，则 $\beta$ 是 $26$ 次本原单位根。显然

${({x^3} + 2x + 1)^*} = {x^3} + 2{x^2} + 1$

(19)

设 $C = ((x - 1)({x^3} + 2x + 1)({x^3} + 2{x^2} + 1),u(x - 1))$ 是环 $R$ 上长度为 $26$ 的循环码。由推论2， $\phi (C)$ 是3元 $[52,44,4]$ LCD码，且 ${\text{Res}}(C)$ 是3元[26,19,4] LCD码。由码表^[39]，长度为52维数为44的3元线性码的Hamming距离的已知最大值为 $4$ 。因此， $\phi (C)$ 是已知参数最好的3元LCD码。同理，由码表^[39]，存在3元[26,19,5]线性码。因此， ${\text{Res}}(C)$ 是几乎最优的3元LCD码。

最后，将本文构造的3元LCD码与现有文献进行比较。文献[18]利用组合的方法构造了3元

$[({3^m} - 1)/2,m,{3^{m - 1}} - m]$

(20)

LCD码。文献[21]利用J-仿射变种码的子域子码，构造了长度满足一定约束条件的3元LCD码。文献[22]利用定义集方法构造了几类LCD码。文献[26]构造了长度 $n \le 20$ 的3元LCD码。文献[33]利用定义集方法构造了Hamming距离为3的最优LCD码。通过比较发现，本文构造了新参数的3元LCD码。与线性码的理论界和码表比较，本文构造的4类3元LCD码具有较好的参数。

4. 结束语

本文通过引入 ${R^n}$ 到 $\mathbb{F}_3^{2n}$ 的Gray映射，给出了环 $R$ 上长度为 $n$ 的循环码的Gray象是长度为 $2n$ 的3元LCD码的充分条件。利用环 $R$ 上循环码的Gray象，构造了4类参数好的3元LCD码。研究结果表明，本文提出的方法可以构造参数好的3元LCD码。分析本文构造的3元LCD码的编码与译码复杂度以及构造Hamming距离大于4的最优3元LCD码是进一步的研究问题。

图 1 云雾混合车联网网络架构

下载: 全尺寸图片幻灯片

图 2 节省能量与时延阈值的关系

下载: 全尺寸图片幻灯片

图 3 平均资源成本与雾节点数量的关系

下载: 全尺寸图片幻灯片

图 4 总能量消耗与雾节点用户数的关系

下载: 全尺寸图片幻灯片

图 5 平均时延与雾节点数量的关系

下载: 全尺寸图片幻灯片

图 6 违反概率与卸载用户数的关系

下载: 全尺寸图片幻灯片

表 1 联合卸载决策和基于二分法的计算资源调度算法

1. 初始化试验次数 $J$ ，用户数 $M$ ，总带宽 $B_f^{\max }$ 及资源块带宽 ${B_{SC}}$ 　　及总计算资源 ${F^{{\rm{fog}}}}$ ，初始化用户参数 ${D_m}$ , ${u_m}$ , $f_m^{{\rm{loc}}}$ , $p_m^{\max }$ , $p_m^{{\rm{id}}}$ , $p_m^{{\rm{loc}}}$ , $R_m^{{\rm{fc}}}$ , $f_m^c$ , $d_m^{\max }$ ，初始化式(17)中的所有矩阵
2. 利用凸优化工具求解式(17)得到优化解 ${{{Q}}^*}$
3. 从优化解 ${{{Q}}^{\rm{}}}$ 中提取左上角 $2M \times 2M$ 的子矩阵 ${{{Q}}^{'}}$ , ${{{Q}}^{'*}}$ 中的　　对角线上的元素值为 $\Pr = \left[ { {\rm{pr} }_1^f,{\rm{pr} }_1^{\rm c},...,{\rm{pr} }_M^f,{\rm{pr} }_M^{\rm c}} \right]$
4. for $j = 1;j \le J;j + +$ do
5. 　根据式(18)从 $\Pr$ 中提取卸载决策 ${{{v}}^j}$
6. 　执行计算资源调度：初始化参数 ${\chi ^{\min }} = \max \{ {S_m}\} ,\,{\chi ^{\max } } =$ 　　　 $\displaystyle\sum\limits_m {\left( {\frac{ { {C_m}p_m^{ {\rm{id} } }M} }{ { {F^{ {\rm{fog} } } } } } + {S_m} } \right)}$ ，于是有 ${\chi ^{\min }} \le {\chi ^{{\rm{opt}}}} \le {\chi ^{\max }}$ ，最大　　　可容忍误差 $\varepsilon > 0$ , ${\chi ^j}{\rm{ = (}}{\chi ^{\min }} + {\chi ^{\max }}{\rm{)/2}}$
7. while $\|{\chi ^{\max }} - {\chi ^{\min }}\| \ge \varepsilon$ do 　8. 　　if $\displaystyle\sum\limits_{m \in M} {\frac{ { {C_m}p_m^{ {\rm{id} } } }}{ { {\chi ^j} - {S_m} } } > {F^{ {\rm{fog} } } }}$ then
9. 　　　 ${\chi ^{\min }} = {\chi ^j}$
10. 　　else
11. 　　　 ${\chi ^{\max }} = {\chi ^j}$
12. 　　end if
13. end while
14. 　if $\|{\chi ^{\max }} - {\chi ^{\min }}\| \le \varepsilon$ then
15. 　　 ${\chi ^{{\rm{opt}}}} = {\chi ^j}$
16. end if
17. 将得到的 ${\chi ^{{\rm{opt}}}}$ 代入式(21)得到计算资源调度策略 ${{{f}}^{{\rm{fog}}}}$
18. end for

下载: 导出CSV

表 2 基于在线测量的接入控制算法

1. 初始化每个雾节点的资源块配置数量 $z$ 和剩余资源块数量 $B$ ，在周期 $n$ 上观察每个雾节点 $f$ 的接入请求队列状态 $Q_n^f$
2. for $f = 1;f < F;f + +$ do
3. 　计算 $a_{\rm o}^f$ ，估计 ${\mathop m\limits^{\wedge} } _{\rm o}^f$
4. while $Q_n^f \ge B_H^f$ or $B = \emptyset$ do
5. 　 $z \leftarrow z + 1$ ， ${C_f}(n) \leftarrow z\mathop r\limits^\_$ ， $B \leftarrow B - 1$
6. end while
7. 计算 $a_{\rm o}^f$ 及 $\hat m_{\rm o}^f$
8. if $Q_n^f < B_H^f$ & $\hat m_{\rm o}^f \ge a_{\rm o}^f$ then
9. $z \leftarrow z + {\Delta _1}$ ， ${C_f}(n) \leftarrow z\mathop r\limits^\_$ ， $B \leftarrow B - {\Delta _1}$
10. 　else if $Q_n^f < B_H^f$ & $\hat m_{\rm o}^f \ge a_{\rm o}^f$ then
11. 　　式(24)执行黄金分割搜索算法估计 $\hat P_{n + N}^f$
12. 　　if $\hat P_{n + N}^f \ge {\varepsilon _f}$ then
13. 　　 $z \leftarrow z + {\Delta _2}$ , ${C_f}(n) \leftarrow z\mathop r\limits^\_$ , $B \leftarrow B - {\Delta _2}$
14. 　　end if
15. 　end if
16. end if
17. end for

下载: 导出CSV

表 3 基于迭代的带宽和功率资源调度

1. 初始化迭代次数 ${N_1}{\rm{ = }}0$ 和 ${N_2}{\rm{ = }}0$ ，误差精度 ${\delta _1}$ 和 ${\delta _2}$ , ${V^{{N_1}}}{\rm{ = }}1$
2. while ${N_1} < {N_{1\max }}$ do
3. 　while ${N_2} < {N_{2\max }}$ do
4. 　　对给定的 ${V^{{N_1}}}$ ，根据式(31)求得优化的传输功率解
5. 　　在区间 $[0,1]$ 内执行二分搜索方法求解 ${\varphi _m}({N_2})$ ，并将　　　　 ${\varphi _m}({N_2})$ 代入式(34)求解带宽资源调度方案
6. 　　　通过次梯度法分别更新拉格朗日乘子
7. 　　if ${\rm{\|\|}}\beta ({N_2} + 1) - \beta ({N_2})\|{\|_2} < {\delta _2}$ , 　　　　 $\|\|\eta ({N_2} + 1) - \eta ({N_2})\|{\|_2} < {\delta _2}$ , 　　　　 $\|\|\mu ({N_2} + 1) - \mu ({N_2})\|{\|_2} < {\delta _2}$ , 　　　　 $\|\|\pi ({N_2} + 1) - \pi ({N_2})\|{\|_2} < {\delta _2}$ then
8. 　　　　 $\alpha _m^{{N_1}} = {\alpha _m}({N_2})$ , $p_m^{{\rm{com}}{{\rm{N}}_1}} = p_m^{{\rm{com}}}\left( {{N_2}} \right)$ , break
9. 　else
10. 　　 ${N_2} = {N_2} + 1$
11. 　end if
12. 　end while
13. 　if $\left\| { {D_m}p_m^{ {\rm{com} }{ {\rm{N} }_{\rm{1} } } } - {V^{ {N_1} } }\alpha _m^{ {N_1} }\lg \left( {1 + \dfrac{ {p_m^{ {\rm{com} }{ {\rm{N} }_{\rm{1} } } }{h_m} } }{ {\alpha _m^{ {N_1} }{N_0}{B_{ {\rm{SC} } } } } } } \right)} \right\| < {\delta _1}$ then
14. 　　　 $\{ {{{p}}^},{{{\alpha}} ^}\} = \{ {{{p}}^{{\rm{com}}{{\rm{N}}_{\rm{1}}}}},{{{\alpha}} ^{{N_1}}}\}$
15. 　else
16. 　　　令 ${V^{ {N_1} + 1} } \!\!=\! {D_m}p_m^{ {\rm{com} }{ {\rm{N} }_{\rm{1} } } }/\alpha _m^{ {N_1} }{B_{ {\rm{SC} } } }\lg \!\left( {1 \!+\! \dfrac{ {p_m^{ {\rm{com} }{ {\rm{N} }_{\rm{1} } } }{h_m} } }{ {\alpha _m^{ {N_1} }{N_0}{B_{ {\rm{SC} } } } } } } \right)$
17. 　　end if
18. end while
19. 输出无线资源调度优化解 ${{{p}}^}$ , ${{{\alpha}} ^}$

下载: 导出CSV

表 4 仿真参数

参数	数值
系统带宽	10 MHz(50PRBs)
路径损耗模型	UrbanMicro(UMi)
最大传输功率	23 dBm
计算资源单价	0.10, 0.15, 0.20 unit/cycle
计算密度	297.62 cycle/bit
链路传输速率	1 Mb/s

参数	数值
卸载业务到达	泊松分布
莱斯因子	6 dB
滑动窗口大小	60 ms
平滑指数	0.7
雾计算资源量	1 G cycle
云层计算能力	2 G cycle/s

参数	数值
比特到达速率	0.4 Mbit/ms
噪声功率	–174 dBm/Hz
PRB单价	1, 1.5, 2 unit/PRB
仿真时间	6000 ms
队列上溢概率	0.2
单位 $t$ 功率消耗	0.01 W

下载: 导出CSV

参考文献(16)

MEBREK A, MERGHEM-BOULAHIA L, and ESSEGHIR M. Efficient green solution for a balanced energy consumption and delay in the IoT-Fog-Cloud computing[C]. The 16th IEEE International Symposium on Network Computing and Applications, Cambridge, USA, 2017: 1–4. doi: 10.1109/NCA.2017.8171359.

BACCARELLI E, NARANJO P G V, SCARPINITI M, et al. Fog of everything: Energy-efficient networked computing architectures, research challenges, and a case study[J]. IEEE Access, 2017, 5: 9882–9910. doi: 10.1109/ACCESS.2017.2702013

LIU Kaiyang, PENG Jun, ZHANG Xiaoyong, et al. A combinatorial optimization for energy-efficient mobile cloud offloading over cellular networks[C]. 2016 IEEE Global Communications Conference, Washington, USA, 2016: 1–6. doi: 10.1109/GLOCOM.2016.7841488.

YANG Lei, CAO Jiannong, TANG Shaojie, et al. A framework for partitioning and execution of data stream applications in mobile cloud computing[C]. The 5th IEEE International Conference on Cloud Computing, Honolulu, USA, 2012: 794–802. doi: 10.1109/CLOUD.2012.97.

LIU Mengyu and LIU Yuan. Price-based distributed offloading for mobile-edge computing with computation capacity constraints[J]. IEEE Wireless Communications Letters, 2018, 7(3): 420–423. doi: 10.1109/LWC.2017.2780128

CAO Xiaowen, WANG Feng, XU Jie, et al. Joint computation and communication cooperation for energy-efficient mobile edge computing[J]. IEEE Internet of Things Journal, 2019, 6(3): 4188–4200. doi: 10.1109/JIOT.2018.2875246

MENG Xianling, WANG Wei, and ZHANG Zhaoyang. Delay-constrained hybrid computation offloading with cloud and fog computing[J]. IEEE Access, 2017, 5: 21355–21367. doi: 10.1109/ACCESS.2017.2748140

GU H Y, YANG C Y, and FONG B. Low-complexity centralized joint power and admission control in cognitive radio networks[J]. IEEE Communications Letters, 2009, 13(6): 420–422. doi: 10.1109/LCOMM.2009.082173

JIANG Menglan, CONDOLUCI M, and MAHMOODI T. Network slicing management & prioritization in 5G mobile systems[C]. The 22th European Wireless Conference, Oulu, Finland, 2016: 1–6.

YAQOOB S, ULLAH A, AKBAR M, et al. Fog-assisted congestion avoidance scheme for internet of vehicles[C]. The 14th International Wireless Communications & Mobile Computing Conference, Limassol, Cyprus, 2018: 618–622. doi: 10.1109/IWCMC.2018.8450402.

LI Jian, PENG Mugen, YU Yuling, et al. Energy-efficient joint congestion control and resource optimization in heterogeneous cloud radio access networks[J]. IEEE Transactions on Vehicular Technology, 2016, 65(12): 9873–9887. doi: 10.1109/TVT.2016.2531184

LIU Yiming, YU F R, LI Xi, et al. Distributed resource allocation and computation offloading in fog and cloud networks with non-orthogonal multiple access[J]. IEEE Transactions on Vehicular Technology, 2018, 67(12): 12137–12151. doi: 10.1109/TVT.2018.2872912

LI Qiuping, ZHAO Junhui, GONG Yi, et al. Energy-efficient computation offloading and resource allocation in fog computing for internet of everything[J]. China Communications, 2019, 16(3): 32–41.

SHAHZADI R, NIAZ A, ALI M, et al. Three tier fog networks: Enabling IoT/5G for latency sensitive applications[J]. China Communications, 2019, 16(3): 1–11.

SOOKHAK M, YU F R, HE Ying, et al. Fog vehicular computing: Augmentation of fog computing using vehicular cloud computing[J]. IEEE Vehicular Technology Magazine, 2017, 12(3): 55–64. doi: 10.1109/MVT.2017.2667499

LI Di, KAR S, and CUI Shuguang. Distributed quickest detection in sensor networks via two-layer large deviation analysis[J]. IEEE Internet of Things Journal, 2018, 5(2): 930–942. doi: 10.1109/JIOT.2018.2810825

施引文献

资源附件(0)

访问统计

图(6) / 表(4)

计量

文章访问数: 2114
HTML全文浏览量: 750
PDF下载量: 139
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

基于云雾混合计算的车联网联合资源分配算法

doi: 10.11999/JEIT190306

通讯作者:
肖娇　Ir_xiao@163.com

计量

Joint Resource Allocation Algorithms Based on Mixed Cloud/Fog Computing in Vehicular Network

1. 引言

2. 预备知识

3. 3元LCD码的构造

4. 结束语

计量

目录

1. 引言

2. 预备知识

3. 3元LCD码的构造

4. 结束语

留言板

基于云雾混合计算的车联网联合资源分配算法

doi: 10.11999/JEIT190306

通讯作者: 肖娇 Ir_xiao@163.com

计量

出版历程

Joint Resource Allocation Algorithms Based on Mixed Cloud/Fog Computing in Vehicular Network

1. 引言

2. 预备知识

3. 3元LCD码的构造

4. 结束语

计量

出版历程

目录

1. 引言

2. 预备知识

3. 3元LCD码的构造

4. 结束语

通讯作者:
肖娇　Ir_xiao@163.com