·966· 工程科学学报，第39卷，第6期 进行建模分析，从网络运行环境中获取信息，还要对其 将式(17)、(22)带入式(24)并结合节点历史信息 他节点的状态和行为动机进行合理地判断，从而选择 便可以求出任意节点i的效用函数 最佳的合作对象 2.2数据转发策略 为了科学合理地选择最佳下一跳中继节点， 根据帕累托最优基本理论，ICWN中的资源最优 EEDFS综合考虑上述参数，对网络进行扩展式动态博 分配问题即上一跳给定节点i与其邻居节点集合Nei- 弈建模分析.根据网络特性作出以下假设：(1)网络 L之间的数据转发服务分配问题，两跳节点之间的一 节点的服务能力具有一定的差异性，随着网络的运行， 次会话是一次博弈过程.表1为一次博弈矩阵. 节点自身转发服务能力也在实时变化；(2)节点初始 表1节点：和j的博弈矩阵 能量不相同：(3)节点所追求自身生存周期和效用均 Table 1 Game matrix of nodes i and j 为最佳：(4)即使活跃节点也有一定的自私性，需要用 状态 转发 不转发 数据转发率客观地衡量节点转发服务概率，剩余能量 转发 (F,F,) (F,-n) 的水平直接决定着节点的转发服务能力 不转发 (-n,F,) (-n,-） 帕累托最优[]是博弈论中解决资源最优分配问 题的一种理想方法，能够保障资源分配过程的相对公 由上述矩阵可知，在节点选择转发时，其收益为对 平和效率.这种最优是资源配置的一种状态，其他任 应的效用函数，反之，节点选择不转发的收益为负.在 何形式的资源配置，均不可能满足使得至少一个节点 选择合作的节点时，虽然为其他节点转发数据会消耗 收益而不致使其他节点利益受损.如前所述，可将IC 一定的资源，但是在转发服务过程中也将获得收益，因 WN中最佳下一跳中继节点的选择看作资源配置问 此，只要收益函数大于代价函数即可；而如果节点选择 题，但是“热点”问题的存在，要求必须高效地配置稀 不合作，则其收益只能为负，所以与选择不合作转发相 缺的网络资源，使得有限的网络资源得到最大地利用. 比，选择合作转发将获得更大的收益 将网络中所有节点看作博弈的有限个参与者，用 经过一次博弈后，一次会话完成一次匹配过程： 集合N={1,2,…,n}表示，节点的策略集空间为S= F:i→NeiL,且NeiL,≠O.如果将单次会话应用到多次 {s,2,…,5.},3={0,1}表示节点i的策略选择，0表 会话中，节点间数据转发过程便可以看作是有限次重 示转发，1表示不转发，且策略选择只能为0或1. 复博弈过程[2如]，经过多次重复博弈，各节点的效用达 s:∈S:是除了i之外所有参与者的策略选择，则任一 到帕累托最优，最终选取最佳下一跳中继节点.通过 策略组合可表示为s=(s,s).参与者i在该策略组 博弈论解决资源分配问题时，并非每个模型都存在帕 合下的效用函数为F:(s,s),由收益函数门：(s,s-) 累托最优，为此，本节中将证明所提EEDFS中存在帕 和代价函数n(s,s)构成. 累托最优，假设N个节点参与的博弈G,每一跳都存在 由于节点的自私性，节点会降低自身能耗以其延 帕累托最优.根据帕累托最优理论可知，节点在最优 长网络生存时间.因此，可以将节点i的代价函数看作 状态时不可能在保证其他节点的收益不减少的情况下 是节点能量损耗和节点生存时间的函数，由于在节点i 使得至少一个节点收益提高.若当前节点i有M个邻 为其他节点提供转发数据服务的过程中，剩余能量直 居节点，则可以构成M个匹配过程，并选取最佳匹配 接决定网络生存时间，所以将给定节点i在策略组合 max(F:,F:),j∈NeiL,具体过程如图1所示 中消耗的剩余能量百分比作为代价函数： W=0.6Ea-2Enne=40一 E(t) W=1/M （d)） (22) E=3 F=0.8×1/M-2/40 E =30 由于节点的转发意愿能够直接体现任意节点i为 W=0.5Eta-2Ee=30 其他节点提供转发服务的可能性，同时可以间接反应 F=0.8x1/M-2/30 其他节点为给定节点i提供转发服务的概率大小.因 此，i的收益函数可定义为： F=0.8x×0.6-3/30 刀：=AW (23) Fm-0.8x0.5-3/30 式中，入>0为调节系数，体现网络整体自私性，与具体 网络环境有关 图1帕累托最优匹配过程 Fig.1 Pareto optimal matching process 进而，任意节点的效用函数可表示为： F:=n:-7=AW-n:. (24) 由表1结果可知，只有在上一跳节点和下一跳节工程科学学报,第 39 卷,第 6 期 进行建模分析,从网络运行环境中获取信息,还要对其 他节点的状态和行为动机进行合理地判断,从而选择 最佳的合作对象. 为了 科 学 合 理 地 选 择 最 佳 下 一 跳 中 继 节 点, EEDFS综合考虑上述参数,对网络进行扩展式动态博 弈建模分析. 根据网络特性作出以下假设:(1) 网络 节点的服务能力具有一定的差异性,随着网络的运行, 节点自身转发服务能力也在实时变化;(2) 节点初始 能量不相同;(3) 节点所追求自身生存周期和效用均 为最佳;(4) 即使活跃节点也有一定的自私性,需要用 数据转发率客观地衡量节点转发服务概率,剩余能量 的水平直接决定着节点的转发服务能力. 帕累托最优[19] 是博弈论中解决资源最优分配问 题的一种理想方法,能够保障资源分配过程的相对公 平和效率. 这种最优是资源配置的一种状态,其他任 何形式的资源配置,均不可能满足使得至少一个节点 收益而不致使其他节点利益受损. 如前所述,可将 IC鄄 WN 中最佳下一跳中继节点的选择看作资源配置问 题,但是“热点冶问题的存在,要求必须高效地配置稀 缺的网络资源,使得有限的网络资源得到最大地利用. 将网络中所有节点看作博弈的有限个参与者,用 集合 N = {1,2,…,n}表示,节点的策略集空间为 S = {s1 ,s2 ,…,sn },si = {0,1}表示节点 i 的策略选择,0 表 示转发,1 表示不转发,且策略选择只能为 0 或 1. s - i沂S - i是除了 i 之外所有参与者的策略选择,则任一 策略组合可表示为 s = ( si,s - i). 参与者 i 在该策略组 合下的效用函数为 Fi(si,s - i ),由收益函数 浊i ( si,s - i ) 和代价函数 浊 * i (si,s - i)构成. 由于节点的自私性,节点会降低自身能耗以其延 长网络生存时间. 因此,可以将节点 i 的代价函数看作 是节点能量损耗和节点生存时间的函数,由于在节点 i 为其他节点提供转发数据服务的过程中,剩余能量直 接决定网络生存时间,所以将给定节点 i 在策略组合 中消耗的剩余能量百分比作为代价函数: 浊 * i = E i total(t) E i remaining(t) . (22) 由于节点的转发意愿能够直接体现任意节点 i 为 其他节点提供转发服务的可能性,同时可以间接反应 其他节点为给定节点 i 提供转发服务的概率大小. 因 此,i 的收益函数可定义为: 浊i = 姿Wi . (23) 式中,姿 > 0 为调节系数,体现网络整体自私性,与具体 网络环境有关. 进而,任意节点 i 的效用函数可表示为: Fi = 浊i - 浊 * i = 姿Wi - 浊 * i . (24) 将式(17)、(22)带入式(24)并结合节点历史信息 便可以求出任意节点 i 的效用函数. 2郾 2 数据转发策略 根据帕累托最优基本理论,ICWN 中的资源最优 分配问题即上一跳给定节点 i 与其邻居节点集合 Nei鄄 L i 之间的数据转发服务分配问题,两跳节点之间的一 次会话是一次博弈过程. 表 1 为一次博弈矩阵. 表 1 节点 i 和 j 的博弈矩阵 Table 1 Game matrix of nodes i and j 状态 转发 不转发 转发 (Fi,Fj) (Fi, - 浊j) 不转发 ( - 浊i,Fj) ( - 浊i, - 浊j) 由上述矩阵可知,在节点选择转发时,其收益为对 应的效用函数,反之,节点选择不转发的收益为负. 在 选择合作的节点时,虽然为其他节点转发数据会消耗 一定的资源,但是在转发服务过程中也将获得收益,因 此,只要收益函数大于代价函数即可;而如果节点选择 不合作,则其收益只能为负,所以与选择不合作转发相 比,选择合作转发将获得更大的收益. 经过一次博弈后,一次会话完成一次匹配过程: F:i寅NeiLi 且 NeiLi屹芰. 如果将单次会话应用到多次 会话中,节点间数据转发过程便可以看作是有限次重 复博弈过程[20] ,经过多次重复博弈,各节点的效用达 到帕累托最优,最终选取最佳下一跳中继节点. 通过 博弈论解决资源分配问题时,并非每个模型都存在帕 累托最优,为此,本节中将证明所提 EEDFS 中存在帕 累托最优,假设 N 个节点参与的博弈 G,每一跳都存在 帕累托最优. 根据帕累托最优理论可知,节点在最优 状态时不可能在保证其他节点的收益不减少的情况下 使得至少一个节点收益提高. 若当前节点 i 有 M 个邻 居节点,则可以构成 M 个匹配过程,并选取最佳匹配 max(Fi,Fj), j沂NeiL i ,具体过程如图 1 所示. 图 1 帕累托最优匹配过程 Fig. 1 Pareto optimal matching process 由表 1 结果可知,只有在上一跳节点和下一跳节 ·966·