[0082] 为了更清楚地说明本发明实施例,下面将对照附图说明本发明的具体实施方式。显而易见地,下面描述中的附图仅仅是本发明的一些实施例,对于本领域普通技术人员来讲,在不付出创造性劳动的前提下,还可以根据这些附图获得其他的附图,并获得其他的实施方式。
[0083] 如图1所示,本发明实施例的无线体域网能耗和时延加权最小的安全路由选择方法,包括以下流程:
[0084] S1、初始化阶段,各节点获得网络的基本状态信息并得到节点间的配置参数;
[0085] S2、根据网络状态信息,以最小化加权的能耗和时延为目标函数,以无线体域网安全中断概率和连接成功概率为约束,建立离散马尔科夫链优化模型;
[0086] S3、将决策问题分为多个时间阶段,通过贝尔曼方程的价值函数,把一阶段的最优解转化为下一阶段最优解的子问题,因此由最终状态的最优决策迭代求解得初始状态的最优决策;
[0087] S4、通过定义状态的占有率和不确定性来决定下一状态的优先级,同时定义自适应最大深度终止准则;
[0088] S5、基于启发式搜索算法,初始化状态价值的上下边界,利用优先级决定动态规划算法的下一状态选择,并且确定最终能耗和时延的最优安全路由选择策略。
[0089] 其中,上述步骤S1中,在初始化阶段,节点获取节点之间的参数包括邻居节点的信息,通过HELLO包交互获取邻居节点的位置信息,节点通过邻居节点的位置信息可以计算得到与邻居节点之间的距离,以及交换彼此的操作权限信息。
[0090] 上述步骤S2中,步骤S2最终目的是建立离散的马尔科夫链模型,而在马尔科夫链模型中的一个重点就是状态转移概率。这一步骤是定义在选定动作a后,从状态x转移到状态y的状态转移概率。
[0091] 根据与邻居节点之间的距离信息,在选择动作a作为发送节点的情况下从状态x转移到状态y的马尔科夫链状态转移概率πxy(a)表达式如下:
[0092]
[0093] 情况1指从保密消息未被窃听的x状态转移到保密消息未被窃听的邻居y状态;情况2指从保密消息未被窃听的x状态转移到保密消息被窃听的邻居y状态;情况3指从保密消息已经被窃听的x状态转移到保密消息已经被窃听的邻居y状态;情况4指x状态不变的情况;不属于上述4种情况都被归为其他情况。
[0094] 其中,马尔科夫链的状态可以用 来表征。其中, 表示x状态时所有已经解码保密消息的节点集合,ω(x)表示保密消息是否被窃听者窃听。q(a)表示选择动作a为发送节点时的安全中断概率,m代表状态转移过程中增加的已解码节点,p(a,m)表示从节点a发送保密消息到节点m的连接成功概率, 代表节点m属于在从状态x转移到状态y所增加的已解码保密消息的节点集合。由于在本发明中,将合法节点到窃听者之间的信道建模为指数分布,合法节点之间的信道建模为对数正态分布,则q(a)和p(a,m)的表达式分别为
[0095]
[0096]
[0097] 其中,P[·]为概率算子,C(·)表示链路的瞬时频谱效率其单位是bit/s/Hz,a、m和z分别代表发送节点、接收节点和窃听者,dO和dI代表发送节点分别到窃听者和接收节点之间的距离。gO和gI分别定义为从发送节点到窃听者和接收节点的信道增益,其分别服从指数分布和对数正态分布,μ和σ分别代表对数正态分布的均值和标准差。ζ和 分别代表发送速率和保密速率,α为路径损耗因子,ρ代表单位距离的发送信噪比。
[0098] 在本发明的无线体域网模型中,目标是联合优化能耗和时延两个指标,因此第i次状态转移的成本函数c(·)由时延cD(·)和能耗cE(·)两个部分组成,表达式如下:
[0099]
[0100] 其中, 是在这一状态转移过程中接收信号所需要的能耗成本, 是在策略A(·)下状态xi在已经解码保密消息的集合 中选择的中继节点个数,在本发明中为1, 是从状态xi转移到状态xi+1过程中增加的已解码节点的数量, 是考虑这些节点接收所消耗的能量参数。cD=1是时延成本,通过跳数来表征时延。η是代表权值,用于平衡能耗成本和时延成本。
[0101] 根据上述马尔科夫链状态转移概率,以最小化加权的能耗和时延为目标函数,以无线体域网安全中断概率和连接成功概率为约束,建立离散马尔科夫链优化模型,其形式如下:
[0102]
[0103] 在上式中,目标函数定义为联合能耗和时延,i表示第i次状态转移,xi表示第i个状态,E[·]为数学期望算子,c(·)表示状态转移过程中的产生的代价, 代表所有的路由选择策略集合,δ(·)代表在马尔科夫链模型中安全中断的定义,∈代表平均安全中断概率的阈值。
[0104] 约束条件为保密性约束,其阈值为∈,且
[0105]
[0106] 其中,ω(xi)=0表示在此状态下保密消息未被窃听,若被窃听其值为1;
[0107] 利用拉格朗日乘子法将有约束的优化问题转化为无约束的优化问题。
[0108] 对于给定的λ,将加权能耗和时延的成本函数 重新定义为
[0109]
[0110] 相应的,在策略A(·)下给定λ的无约束目标函数 表达式如下,
[0111]
[0112] 其中,x0代表初始状态 集合表示在没有安全中断概率约束的情况下的所有可能策略集,A(·)表示策略函数。
[0113] 上述步骤S3中,利用贝尔曼优化理论中的价值迭代,根据动作a下从状态x转移到状态y的马尔科夫链状态转移概率πxy(a),将优化目标转换成贝尔曼方程形式如下:
[0114]
[0115] 其中,γ∈[0,1)是贝尔曼方程中的折扣因子, 表示状态x的邻居状态集合,A*(·)为最佳策略, 是给定λ和A(·)策略下邻居状态y的目标值, 代表节点a属于状态x已经解码保密消息的节点集合
[0116] 转换后获得状态s的贝尔曼价值函数V(s)形式如下,
[0117]
[0118] 其中,;mina代表选择最佳中继节点使得贝尔曼值函数最小,C(s,a,s′)是在选择动作a时从状态s转移到状态s′的实际成本函数,γ∈[0,1)是贝尔曼方程中的折扣因子,表示状态s的邻居状态集合,用 代表所有吸收状态节点集合,即目标节点已经解码a保密消息的状态,对于目标状态 C(s,a,s′)=0。T (s,s′)表示在动作a下从状态s转移到状态s′的状态转移概率。采用启发式搜索算法的思想,基于先验边界信息hL和hU,采用* *
根据优先级选择后继状态的聚焦实时动态规划算法,获得状态价值的最优值V满足hL≤V≤hU,对于目标状态 hL(s)=hU(s)=0。
[0119] 上述步骤S4中,具体化状态优先级的计算及增量搜索图拓展时边缘状态节点的选π择过程。增量搜索图中的点就是马尔科夫过程中的状态。用W (s)表征在策略π的情况下,状π
态节点s在未到未知区域前每个执行的平均时间步数,在本发明中将W (s)称作在策略π下状态的占有率,表达式如下:
[0120]
[0121] 其中,s0代表初始状态, 且 代表内部状态节点, 代表边缘状态节π点,1‑γ表示在任意时间步数停止的概率。边缘状态节点的W (s)表明其与策略的相关性,π(s)
值越大相关性越大。T (s,s′)表示在策略π下从状态s到状态s′的状态转移概率。
表示状态节点s是不包含吸收状态的内部状态节点。
[0122] 在聚焦实时动态规划算法中,为了选择扩展的边缘状态节点,首先定义一个状态s的超额不确定性Δ(s)
[0123] Δ(s)=|VU(s)‑VL(s)|‑r/2 (12)
[0124] 其中,VU(s)和VL(s)分别表示状态s的状态价值上下限,r表示误差值。
[0125] 根据超额不确定性,获得状态s的优先级f(s)表达式如下,
[0126] f(s)=Δ(s) (13)
[0127]
[0128] 其中,式(13)为边缘状态节点的优先级,式(14)为内部状态节点的优先级。在聚焦*实时动态规划算法中,选择优先级最高的状态节点进行扩展。其中,最佳行动a依据状态价值上限贪婪地选择。在每次更新状态节点时,重新计算优先级f(s)以及边界状态价值上下U L
限V(s)和V(s)。
[0129] 上述步骤S4中,定义聚焦实时动态规划算法的两个试验终止标准:
[0130] 其一,超额不确定度满足条件Δ(s)≤0,则试验终止。
[0131] 其二,H为试验最大深度,当试验到达的深度h≥H时,则试验终止。将H初始化为一个较小的值H0,在本发明中H0=1,根据试验统计作为反馈来自适应地调整H。在反馈机制中,每次试验都会更新质量得分Q,其旨在反应增加探索深度的有用程度,质量得分的表达式如下:
[0132] Q=θW (15)
[0133] 其中,θ代表状态价值上限改变量,W代表状态占有率。在每次试验之后,如果增加最大探索深度的平均质量分数比不增加的更好,则H增加且
[0134] H=kHH (16)
[0135] 其中,kH是每次增加探索深度的比例。
[0136] 本发明适用于无线体域网,在该网络中具有L个合法节点,合法节点之间能够共享和转发消息。同时存在一个窃听者能够窃听保密消息。所有的节点都工作在半双工的模式下,并且以相同的发射功率对保密消息进行传输。在此考虑多跳通信,在每一跳中所有的合法节点都尝试对保密消息解码。当目标节点解码消息时,则停止传输过程。在初始化阶段,节点获取节点之间的参数包括邻居节点的信息,通过HELLO包交互获取邻居节点的位置信息,节点通过邻居节点的位置信息可以计算得到与邻居节点之间的距离,以及交换彼此的操作权限信息。
[0137] 在本发明的无线体域网中,将合法节点之间的信道建模为均值为1的指数分布,并且将合法节点和窃听者之间的信道建模为均值为3.38、标准差为2.8的对数正态分布。已知节点之间的距离以及网络模型,即可由式(1)~(3)计算出马尔科夫链的状态转移概率。
[0138] 在本发明中,优化目标是寻找能耗和时延最小化的安全路由。这里的能耗指消息的接收并解码消息所需要消耗的能量。因此当一次状态转移过程中增加的已解码保密消息的节点越多,能耗越大。目标函数表达式如下:
[0139]
[0140] 其中, 是在这一状态转移过程中接收信号所需要的能耗成本, 是在状态xi下选择中继的节点个数,在本发明中为1,是从状态xi转移到状态xi+1过程中增加的已解码节点的数量, 是考虑这些节点接收所消耗的能量参数。cD=1是时延成本,通过跳数来表征时延。η是代表权值,用于平衡能耗成本和时延成本。
[0141] 为解决式(8)的无约束马尔科夫链优化目标,采用实时动态规划和启发式算法的思想,进一步转换后获得贝尔曼价值函数形式如下,
[0142]
[0143] 其中,C(s,a,s′)是实值成本函数,对于目标状态 C(s,a,s′)=0。启发式搜索*算法基于先验边界信息hL和hU,最优值满足hL≤V≤hU,对于目标状态 hL(s)=hU(s)=
0。
[0144] 图2是增量搜索图的示意图,如图中所示长方形代表的点就是马尔科夫链状态转移过程中的状态。在本发明中,状态其一指保密消息是否被窃听者窃听;其二指此刻已经解码保密消息的合法节点集合。灰色的是已经有后继状态的点为内部状态节点,而其他的没有后继状态的节点为边缘状态节点,即待扩展的状态节点。图中圆形代表马尔科夫过程中的动作。灰色的是在此次状态转移过程中所选择的最佳动作。而图中的P表示在选定动作的条件下,状态转移的概率。
[0145] 本发明主要是在增量搜索图中,针对不同的动作,用式(18)计算对应的状态价值*上下限,即可根据状态价值上限选择出最佳的动作a ,并且根据后继状态的优先级来选择最佳的边缘节点来扩展增量搜索图,直到状态转移到吸收状态,返回更新状态价值上下限和优先级。
[0146] 如图3所示,基于启发式搜索的聚焦实时动态规划算法(FRDTP算法)来解决无线体域网能耗和时延最小的安全路由选择问题,具体步骤如下:
[0147] (1)随机生成一个无线体域网拓扑,计算各节点间的距离,初始化最大探索深度H0,以及初始状态s0的状态价值上限s0U和状态价值下限s0L;
[0148] (2)判断初始状态价值上下限差是否大于r;若是,跳转3);否则,结束试验,获得最小化能耗和时延的随机动态系统控制策略;
[0149] (3)将平均质量分数Q初始化为0,实际探索深度为0,状态s为初始状态,初始状态的占有率W=1;
[0150] (4)根据状态价值上下限和优先级计算公式(13)和(14),遍历所有可选动作,由价值函数式(10)计算出其状态价值,即获得最优动作、选择扩展的状态以及状态价值上限的变化量;
[0151] (5)根据式(15)更新质量分数,判断是否满足任一试验终止准则;若满足则返回更*新状态价值上下限和优先级;否则,更新s=s , h=h+1,跳转至步骤(4);其*
中,s为选择扩展的状态;
[0152] (6)通过比较增加探索深度后的平均质量分数是否更好,即是否满足Q后/h后>Q前/h前;若是,则增加最大探索深度;否则,不增加最大探索深度;
[0153] (7)跳转至步骤(2)。
[0154] 由于消息在传输过程中,状态转移是随机的,图4是就是某一状态转移过程。在状态S中,第一位的0或者1用于表示在该状态下消息是否被窃听,随后的数字表示在该状态下已经解码消息的节点编号。其中S0={0,1}为初始状态,已解码消息的节点只有源节点(节点1)且此状态下消息未被窃听者窃听。初始状态选择源节点1为发送节点,并且根据后继状态的优先级,选择出下一状态为S1={0,1,3,4}。此时根据状态价值上限,在1、3、4这几个已经解码消息的节点中选出最佳的发送节点3。同理可得下一状态为S2={1,1,3,4,2,5},此状态下最佳的发送节点为2。最后,转移到吸收状态S3={1,1,3,4,2,5,6}。图5是简单100×100的无线体域网仿真区域,(0,0)处的1是源节点,(100,100)处的6是目标节点,相当于无线体域网中用于处理数据的中心节点,*点为窃听者,将会窃听保密消息,其他节点都是无线体域网中合法的传感器节点。1→3→2→6是图4状态转移情况下的最佳路由。
[0155] 以上对本发明的主要特征和具体实施例进行了具体且详细的描述,但是本发明不受上述实施例的限制,这也只是一种可行的实施方式。本领域的科研人员可以根据本发明的思想,对实施例进行改进或者变型,这些变型和改进都落入要求保护的本发明范围内。