映射算法

映射算法（共7篇）

映射算法 篇1

1 引言

网络中的数据源之间存在大量映射关系。图1给出了一个数据共享网络的拓扑结构示意图。当数据源E需要获取集成模式下的数据时需要将E上的查询通过E到C、C到A和A到集成模式之间的映射关系,转发到集成模式上。当E到集成模式的映射路径不唯一时,返回的数据结果可能不同。在数据交换中,为得到可靠的数据,需要得到所有映射路径,当数据源规模庞大时,执行的代价很高。尤其当某个节点,例如C离开网络时,E到集成模式的映射路径将断开,此时会造成数据的丢失,映射组合可以较好的解决该问题,通过预先组合映射路径上的映射,可以直接得到数据交换对象之间的映射关系,节省查询在映射链上传递带来的开销。

随着时间的推移、应用需求的变更以及系统的更新换代,数据源间原有的直接映射演变成了间接映射,在映射组合时需要间接映射带来的影响。大部分组合映射的研究对象主要是直接映射[1,2,3,4,5],包括基于逻辑的方法、基于约束关系的方法以及模式转换的方法[5,6,7]等。基于转换的方法需要定义复杂的模式转换操作,不支持包含复杂模式结构元素组合运算的间接映射;现有的非直接映射的研究主要考虑目标和源模式之间的非直接映射定义以及基本操作[8],而很少考虑组合问题。

Yu和Popa等讨论了嵌套关系模式下基于SOtgd[3]的映射组合问题。提出一种映射组合算法,支持嵌套模式。Nash等[4]研究了非source-to-target情况下一阶逻辑约束描述的映射组合问题。Berstein等研究了非source-to-targe下的映射组合问题[9],扩展了Nash和Fagin等的工作。映射组合的求解主要采用逐步消除中间模式符号(记为BECA)的方式,然而Berstein等也说明了某些情况下中间模式可能无法完全被消除,此时不是完全意义上的组合映射,主要原因是间接映射的存在。本文主要研究间接映射的组合机制,给出了间接映射的组合算法和实验分析。

2 映射组合概述

定义1令R1、R2为二元关系,R1和R2的组合R1°R2定义为二元关系:,“°”为组合运算符号。

令Inst(M)表示映射的实例,下面利用二元关系Inst(M12)和Inst(M23)来定义映射M12和M23的组合。

定义2[3]令为两个映射模型,其中S1,S2,S3两两没有公共元素符号。当Inst(M)=Inst(M12)°Inst(M23)时,映射为M12和M23的组合映射,满足,其中Ii为模式Si的实例,1≤i≤3。

图2给出了以S2为中间模式、S2的实例为中间实例的直接映射组合,实现在已知M12和M23的情况下S1和S3的直接数据交换。

3 间接映射定义

间接映射是指源模式的某个或若干节点的实例经过一定的代数运算后映射到目标模式的某个或若干节点实例的代数运算结果上,如图3所示。

在映射[1]中,方框中的节点实例经过代数运算后整体映射到目标模式的一个元素的上。下面给出代数运算定义。

定义3间接模式元素关联定义为具有间接映射关系的模式元素的关联关系集合。令φS为S的公式集合,Si为S的Scheme,则代数运算具有下面的四种形式,这里用模式来代替对应的实例集合:

(1)并集映射:具有类似的形式

(2)笛卡尔积映射:

(3)投影映射,表示为:

(4)选择操作映射:

令为模式元素的代数运算操作符,间接映射下的源模式公式可表示为:。以图4为例,M12表示为:

4 间接映射组合机制

考虑图4给出的映射关系,虽然M12和M23有公共的模式S2,但无法根据M12和M23直接建立S1到S3的映射关系,更无法直接给出组合映射的表达式。如果直接进行组合,S1只能映射到S3某个元素的一部分,在数据交换时,需要S2下实例的参与才能得到S3下完整的实例,因此根据直接映射组合进行数据交换时可能丢失信息。本文提出算法的主要思想是构建一个可进行直接映射组合的扩充模式,并保证该模式实例与原有模式的实例在广义同态函数下同构。采用基于中间模式的模式元素数据回流策略,定义扩展模式,实现间接映射的组合。相比BECA方法,数据回流能够消除中间模式的影响。

定义4令为包含间接映射的映射模型,其中为形如的公式集合,从S到T为广义sound类型映射[10]。令DomM(S)为S的映射域,Dom(T)为T的有效域,有。令T参与间接映射的变量集合为yIn,S参与间接映射的变量集合为xIn,构建S下的虚拟元素集合yIn-xIn。如图5所示,记得到的新源模式为S′,则可以在映射域DomM(DomM(S))上建立T到S′的直接映射。若表示S′到T的映射,则记为的逆映射,虚拟元素的构建过程称为模式元素回流过程,简记为模式回流。

定义5令S1,S2,S3为两两没有公共符号的模式,为间接映射。根据定义4.12构建包含虚拟元素的新的源模式S′1,得到映射,同时根据逆运算构建新映射,得到新的映射模型为。若,即满足:,则称M为M12和M23的组合间接映射。

5 间接映射组合生成算法

图6中,虚线给出了新模式元素与中间模式的对应关系。可以看出,当源模式S1添加虚拟元素成为S′1时,可直接建立S′1到S3的组合映射。同直接映射不同,数据交换时,中间模式的部分元素对应的数据将首先回流到源模式下,在源模式和目标模式的数据交换过程中存在反向数据流动。

5.1 组合算法

基于模式回流的间接模式映射组合的算法(ElementsBackbasedMappingCompositionAlgorithm,简记为EBMC):

Algorithm EBMCInput:映射

Output:映射。

(1)初始化和。对和中的变量和关系进行重命名操作,保证不存在名称相同的变量和模式名称。

(2)数据回流和虚拟元素构建。若存在S1到S2的映射:andS2到S3的映射:,满足,则对所有满足条件的i,取投影操作,得到属性集合E={E1,…El},其中Ei为操作得到的属性集合。

将Ei添加到S1中,并与其对应的进行属性组合,该过程为一个模式回流过程。

(3)S12、S23构建。初始化两个空集合S12、S23,假定的蕴涵式形式为:

将每个中的公式,添加到S12中,类似的处理,得到包含的公式集合S23。对每个S12中的公式,其中x为全称量词量化变量,xj为x上的项,1≤j≤k。

用k个包含原子公式的蕴涵式来替换每个S12中的χ,得到:

(4)S12、S23组合。取S23中的形如ψ※γ的公式χ,对ψ中存在的每个R(y),通过如下步骤用S′1上的原子公式替换R(y)。

令为所有S12中的公式,且其右侧包含R,

若S12中不存在该公式则从S23中移除χ;

否则对的变量进行重命名,使其不与χ中的变量名称重复;

从S23中移除χ,通过如下方式添加p个公式到S23中:将χ中的所有R(y)替换成φi,并将结果添加到S23中(1≤i≤p)。

重复上述步骤,直到S23中的所有公式左侧的子模式符号都来自于S1。

(5)构建M13。令S23=(χ1,…,χr),其中χ1,…,χr为前面得到的蕴涵式,则,其中zi为χi出现的所有变量,1≤i≤r。。

算法给出的组合映射的生成前提是需要维护一个新的源模式,而该模式在其他组合映射中可能无法直接使用,但在大规模数据交换情况下,维护该扩展模式能够提高数据交换效率。

5.2 复杂度分析

令S1、S2和S3所包含的模式元素个数分别为N1、N2和N3,并令初始化和的重命名操作复杂度为O(N1×N2×N3)。

令S2到S3以及S1到S2的映射集合包含的映射元素分别为N23和N12,N12和N23都是原子模式元素(未参与组合运算)的个数。于是模式回流中需要构建的虚拟元素个数为N23-N12,得到构建虚拟元素的复杂度为O(N23-N12)。

组合过程的复杂度由和中所包含的原子公式数量确定。令包含的形如的公式的个数为N 12C,而每个ψi包含的原子公式为n12i个,得到的原子映射集合元素为N 12C×n12i个。若中形如的公式个数为N 23C,其中ψi为原子公式集合,则替换过程中需要匹配的原子公式对的数量为N 12C×n12i×N 23C。于是组合过程的复杂度为O(N 12C×n12i×N 23C)。由此得到模式回流策略下,组合映射生成算法的复杂度为:O(N1×N2×N3)+O(N23-N12)+O(N 12C×n12i×N 23C)。

而直接映射组合过程的复杂度为O(N1×N2×N3)+O(N 12C×n12i×N 23C),二者都是多项式级的复杂度

6 实验分析

考虑图4给出的情况,对S1到S3的数据交换效率进行实验分析,对比在不同数据实例规模下,根据非间接映射组合以及间接映射组合进行S1到S3的数据交换过程执行时间。实验数据库为Oracle,记录读写时间是记录规模与属性数量的增函数。

在非组合映射情况下,S1的数据实例{I1}根据映射M12转换到S2下,记为{I2},{I2}再根据M23转换到S3下,得到{I3}。数据读写主要发生在三个模式之间。在组合映射情况下,采用回流策略,S2部分属性的数据实例首先回流到S1下,得到新的数据实例{I′1},然后根据组合映射M13得到S3下的数据实例{I3}。图7左侧给出了不同数据实例输入规模下,数据交换执行时间的对比。

下面考虑BECA与EBMC的对比,BECA方法通过代数运算来逐步消除中间模式元素,核心思想是通过等价替换,将中间模式的符号尽量的替换成目标和源模式下的符号,因此,消除的模式元素可能分别包含了目标和源模式下元素。实验给定目标模式、源模式以及参与间接映射的中间模式元素规模,令BECA方法中可能参与消除的模式元素数量服从均匀分布,回流模式元素的数量由EBMC算法的第(2)步确定。图7右侧给出BECA消除中间模式元素数量与EBMC模式元素回流数量的对比。

7 结束语

间接映射组合过程中,中间模式对BECA与EBMC两种方式得到组合映射的影响基本相同。同时,EB-MC中回流的元素基本上等于BECA中未消除的元素数量,但IMCA能够完全消除中间模式的影响,实现真正意义的组合。

参考文献

[1]Madhavan J,Halevy A Y.Composing Mappings Among Data Sources.VLDB03,Berlin,Germany,ACM,2003,572-583

[2]Nash A.Foundations of Information Integration:学位论文.SAN DIEGO:UNIVERSITY OF CALIFORNIA,2006.

[3]Fagin R,Kolaitis PG,Popa L.Composing Schema Mappings:Second-Order Dependencies to the Rescue.ACMTODS,2005,30(4):994-1055

[4]Nash A,Berstein PA,Melnik S.Composition of Mappings Given by Embedded Dependencies.PODS2005,Baltimore,Mary-land,USA,ACM,2005.

[5]McBrien P,Poulovassilis A.Data Integration by Bi-Directional Schema Transformation Rules.ICDE03,Boston,USA,IEEE,2003,227-238

[6]Bo.M,Kittivoravitkul S,Lazanitis C,et al.AutoMed:A BAV Data Integration System for Heterogeneous Data Sources.CAiSE04,Riga Latvia,Springer Verlag LNCS,2004,82-97

[7]Bo.M,McBrien P.Comparing and Transforming Between Data Models via an Intermediate Hypergraph Data Model.COMPUT-ER SCIENCE,2005,373069-109.

[8]LiXu,Embley D W.A Composite Approach to Automating Direct and Indirect Schema Mappings.Information System,2006,31(8):697-132

[9]Berstein PA,Green TJ,Melnik S.Implementing mapping composition.VLDB Journal,2008,(17):333-353

[10]Lenzerini M.Data Integration:A Theoretical Perspective.PODS0'2,Madison,Wisconsin,USA,ACM,2002,233-246

空间映射算法优化八木天线 篇2

在现有的文献中,已经介绍了空间优化算法分析微带电路。在分析一个物理系统的响应时,随着所采用分析模型的不同,在计算精度和计算速度上都会有很大的差异。一般而言,精细模型的计算结果准确,但效率低,而粗糙模型的计算精度低,但速度快。在进行优化设计时,传统的优化方法通常利用精细物理模型,以便获得准确、可靠的设计结果,但由于其计算量十分庞大,有可能使优化过程难以实现。另一方面,如果采用不够精细的分析模型,优化过程可以顺利实现,但设计结果却不可靠。因此,寻求一种即具有采用粗糙模型的优化设计效率,同时又具有工程上可接受的设计精度的算法显得十分必要。

在现代电子战和信息战中,敌我识别器的性能具有重要影响。通常用八木天线作为敌我识别天线的一个模型。运用空间映射算法优化敌我识别天线显得非常重要,文中首先介绍了空间映射算法所需要两个模型的基本概念,并在此基础上结合八木天线提出布局优化的目标函数,然后详细论述如何利用空间映射算法和遗传算法实现天线布局的优化配置。

1 数学模型

1.1 矩量法精细模型

在运用矩量法[1]求解天线阵的参量时,为了求解,可以将每一个天线看成是由n个小段连在一起的,如图1所示。每一个小段的两个端点确定了在空间中的一对端点,这N对端点可以想象成一个N端口网络,而短路所有网络的端口就得到了线状物体。阻抗矩阵如下:

$\begin{array}{l}\mathit{{\rm Z}}{}_{mn}=\text{j}\omega \mu \text{Δ}l{}_n\text{Δ}l{}_m\phi (n,m)+(1/\text{j}\omega \epsilon )[\phi (\stackrel{+}{{\displaystyle n}},\stackrel{+}{{\displaystyle m}})-\\ \phi (\overline{n},\stackrel{+}{{\displaystyle m}})-\phi (\stackrel{+}{{\displaystyle n}},\overline{m})+\phi (\overline{n},\overline{m})](1)\end{array}$

式中:n,m分别表示无线的第n,m段。图2所示为两天线段元。

$\phi (n,m)=\frac{1}{\text{Δ}l{}_n}{\displaystyle {\int }_{\text{Δ}l{}_n}\frac{\text{e}{}^{-\text{j}kR{}_m}}{4\text{π}R{}_m}}\text{d}l(2)$

式中:R为距离参量。

本文对式(2)进行近似处理,如果m=n此时(a表示天线元半径)有:

$\phi (n,n)\stackrel{\Delta }{\_}\frac{1}{2\text{π}\text{Δ}l{}_n}\lg \left(\frac{\text{Δ}l{}_n}{a}\right)-\frac{\text{j}k}{4\text{π}}(3)$

若m≠n时,粗糙的近似是将Rm在积分式中作为常数,此时有:

$\phi (m,n)=\frac{\text{e}{}^{-\text{j}kR{}_{mn}}}{4\text{π}R{}_{mn}}(4)$

式中:Δl为天线段元长度。

添加馈电电压就可以求得天线上的电流分布。

$E{}^s(r)=-\text{j}\omega A(r)-\nabla \Phi (r)(5)$

1.2 粗糙模型

用$\left|f(\theta )\right|$表示天线阵的场强幅度方向函数,得:

$\left|f(\theta )\right|=\left|f{}_1(\theta )\right|\cdot \left|f{}_a(\theta )\right|$

其中:

$\left|f{}_a(\theta )\right|={\displaystyle \sum _{i=1}^{n}m}{}_{1i}\text{e}{}^{\text{j}(kd{}_{1i}\cos \theta +\beta {}_{1i})}(6)$

式中:$\left|f{}_1(\theta )\right|$为天线元的方向函数,仅与天线元的形式和尺寸有关;$\left|f{}_a(\theta )\right|$与天线元的元电流分布、空间分布和个数n有关。通过方向图乘积定理,对天线阵进行整体建模,并求得增益。

2运用空间映射算法和遗传算法对天线位置实行优化

经过前面的计算,建立了计算天线增益[2]的两种模型:精细模型和粗糙模型。这两种模型都可以将天线增益看作是因变量,将天线的几何位置当作是自变量。天线增益是衡量天线阵分布好坏的最重要参数,所以用天线增益表达式作为天线布局优化函数的主要组成部分。

实际的天线阵排列时,由于空间有限,在这种情况下得到天线增益最大值所对应的天线位置显得尤为重要,从以前的方法可以看出,矩量法的精细模型优化周期很长(一般需要好多个小时),有时可能时间更长,而无法进行优化,运用矩量法粗糙模型计算很迅速(通常需要几分钟),但计算结果不是很准确,可以看出,用单一的模型进行优化都不是很理想。运用空间映射算法结合遗传算法实现优化过程可以兼顾效率和精度。下面将具体介绍。

空间映射算法[3] (Space Mapping Algorithm,SMA)涉及两个模型,其一是准确,但效率较低的模型,称精细模型(Fine Model);其二是虽不够准确,但十分高效的模型,称粗糙模型(Coarse Model) 。其基本思想是在两个模型的设计参数空间之间建立一种数学联系映射[4]。通过使粗糙模型的响应逼近精细模型的响应,找出粗糙模型中的设计参数,利用已建立起来的映射关系,最终获得精细模型中的设计参数。这样,主要的优化过程是利用遗传算法优化粗糙模型完成的,从而使得整个优化设计的效率大大提高。

SMA算法流程如下:

(1) 优化粗糙模型得到其近似最优解φ*c。

(2) 令φ*c=φ1f,并在其周围进行扰动,建立向量组Bf,仿真响应Rf;

(3) 参数提取,得到Bc,使:

$\parallel R{}_{\text{f}}(\phi {}_{\text{f}})-R{}_{\text{c}}(\phi {}_{\text{c}})\parallel \le \epsilon (7)$

(4) 计算该次迭代的映射Pj,φc=P(φf)。

(5) 计算粗糙模型理想解对应的精细模型参数φmj+1f=P${}_j^{-1}$(φ*c),并得到Rf(φmj+1f)。

(6) 判断响应‖Rf(φmj+1f)-Rc(φ*c)‖≤ε,若成立,则X*f=Xmj+1f即为近似理想解;否则,将Xmj+1f加入向量组Bf中,转步骤(2)。

事实上由于空间映射算法是一种宏观上的逼近算法,它对于具体求解出一个目标函数的最优解是不行的,这种算法进行优化必须借助与其他优化算法来求解遗传算法的最优解[5],通过迭代不断对粗糙模型的最优解进行校正。遗传算法[6]适用于各种各样复杂形式的函数。它的执行条件很简单,只需要搜索方向和相应的适应度函数就可以进行优化,因此空间映射算法[7]可以结合遗传算法实现函数的优化,得到最优解。

3 应用实例

八木天线[8]已广泛应用于米波和分米波通信、雷达、电视以及其他无线电技术设备中。八木天线的优点是结构简单,维修方便,能获得较高的增益。图3是一个八木天线示意图,其中l(i)(i=1～8)分别表示八木天线的八根天线长度;d(i)(i=1～8)表示八根天线分别到第一根天线的距离[9];工作频率为L波段,c=3×108,波长是λ,l(1)=0.49×λ/2,l(2)=0.46×λ/2, l(3)=0.43×λ/2,l(4)=0.43×λ/2,l(5)=0.43×λ/2,l(6)=0.43×λ/2,l(7)=0.43×λ/2,l(8)=0.43×λ/2,d(1)=0,d(2)=0.18×λ,d(3)=0.33×λ,d(4)=0.53×λ,d(5)=0.83×λ,d(6)=1.13×λ,d(7)=1.43×λ,d(8)=1.78×λ。

这是一个八变量优化问题,将间距作为要优化[10]的变量。

空间映射算法首先优化粗糙模型,令φ*c=φ1f,并在φ1f附近进行扰动,将所得精细模型增益最大值的解代入粗糙模型增益求解中,以精细模型和粗糙模型计算得到的最大增益值之差为目标优化函数优化粗糙模型。根据每一组对应的参量,得到精细模型的一组参量矩阵和相对应粗糙模型的一组参量矩阵精细模型基点是在优化完粗糙模型点的附近得到的,对精细模型基点进行参数提取得到粗糙模型的基点,通过精细模型和粗糙模型的基点,得出映射P,并采用遗传算法计算粗糙模型的最优解。在应用空间映射算法进行迭代时,精细模型和粗糙模型的目标函数值误差小于0.5 dB时整个优化过程结束。优化粗糙模型得到最优解φ*c,令φ*c=φ1f,将φ1f参量代到精细模型中,计算精细模型增益图所用的时间为t=85.781 0 s, 精细模型最大增益值Gmax=11.171 6 dB,将此值代到粗糙模型中,以精细模型和粗糙模型计算得到的最大增益差为目标函数,运用遗传算法优化粗糙模型,其计算时间t=4.813 0 s,得出粗糙模型最大增益值Dmax=13.230 2 dB,其中Gmax与Dmax之差不满足条件,进行优化。计算由空间映射算法得到的精细模型的点φ9f,φ9f=[0.012 0.043 6 0.067 3 0.149 0 0.223 6 0.293 4 0.367 9 0.491 8],由于φ9f和对应的φ9c计算的模型增益差不满足公式(7),故需求下一个映射P2,并得到下一个精细点φ10f,φ10f=[0.011 0.047 6 0.088 6 0.159 8 0.212 3 0.292 3 0.347 9 0.482 5]满足式(7),结束优化。φ9f和φ10f是由SMA映射得来的,φ10f就是由最终精细模型得到的解。图4是两个模型最初的增益对比图(虚线表示精细模型增益图,实线表示粗糙模型增益图),图5是两个模型优化完最终的增益对比图。

由图5可以看出,增益图在主瓣匹配得很好,副瓣匹配得不是很好,但其已经满足了最终的条件。在通过将优化好的参量值代入HFSS进行仿真,如图6所示,得到了很好的结果。

证明运用SMA和遗传算法设计天线阵的排列是可行的,通过优化粗糙模型节省了很多时间。

4 结 语

建立天线布局优化的数学模型,精细模型和粗糙模型——由于两种模型都有可取之处,利用空间映射算法将这两种模型联系起来,即可以避免优化精细模型的用时长,又可以使粗糙模型的准确度提高(遗传算法优化本文的精细模型所用的时间是5 h左右,优化粗糙模型

所用的时间是20 min)。精细模型结合高效的算法这一概念考虑了精度和速度的要求,是一种很好的天线布局优化方法。

摘要：天线的最大增益是通过天线合理布局降低它们之间的干扰来实现的。工程中大多采用简单的数学模型并结合测试方法来进行天线布局设计的,但是这种方法效率低且不够精确。运用空间映射算法优化天线阵的位置参量,可以大大提高运算速率,节省时间。根据空间映射算法理论,提出并建立两种模型:一种是运算速度快,但不够精确的粗糙模型,另一种是运算速度较慢,但比较精确的精细模型。通过在这两种模型中建立映射,并利用遗传算法优化粗模型,兼顾精度和速度,从而得到最优解,为实际工程提供理论上的依据。

关键词：空间映射算法,遗传算法,天线阵,最大增益

参考文献

[1]Harrington R F.计算电磁场的矩量法[M].北京:国防工业出版社,1981.

[2]魏文元,宫得明,陈必森.天线原理[M].西安:西北电讯工程学院出版社,1985.

[3]John W Bandler,Radoslaw M Biernacki,Chen Shaohua.Space Mapping Technique for Electromagnetic Optimization[J].IEEE Trans.on Microwave Theory and Techniques,1994,42(12):2 536-2 544.

[4]John W Bandler,Radoslaw M Biernacki,Chen Shaohua.Electromagnetic Optimization Exploiting Aggressive SpaceMapping[J].IEEE Trans.on Microwave Theory and Tech-niques,1995,43(12):2 784-2 882.

[5]袁军,邱扬,刘其中,等.基于空间映射及遗传算法的车载天线优化配置[J].电波科学学报,2006(1):26-32.

[6]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002.

[7]John W Bandler,Cheng Q S,Dakroury S A,et al.SpaceMapping:The State of Art[J].IEEE Trans.on MicrowaveTheory and Techniques,2004:337-361.

[8]陈政,谢拥军,李江,等.复杂平台天线间耦合度预测的逐级等效法[J].现代电子技术,2008,31(15):149-151.

[9]Qiu Yang,Yuan Jun,Tian Jin.Antenna Position OptimalDesign for Reducing Interference[A].2004 InternationalSymposium on EMC Proceedings[C].2004:689-693.

基于组合混沌映射的图像加密算法 篇3

随着网络技术和多媒体技术的迅速发展, 数字图像正在成为人们网络信息交流的重要载体, 所以图像的安全性自然成为人们所关心的问题。传统的加密算法并不适合进行图像加密, 如DES, AES, RSA, 因为用它们加密之后的图象相邻像素点的相关性很大, 不适合保密。应用混沌映射进行图像加密与传统算法相比, 有很多相似但又不同的特性[1,2,3]。例如, 传统加密算法对密钥敏感, 然而混沌映射对初始值和参数值敏感;传统加密算法通过多轮加密来扰乱和扩散数据, 而混沌映射通过迭代把初始区域扩散到整个相空间。传统加密是定义在有限集合, 而混沌映射是定义在实数集。现已有很多的专家学者应用混沌映射进行图像加密, 如YEN J C使用CKBA的加密方法[4];SCHARINGER J使用kolmogorov流的图像加密算法[5];Zhi-Hong Guan使用CAT映射进行图像置换加密[6]等等。

Logistic映射和Chen映射[7]都是典型的混沌映射, 它们都具有初值敏感性和参数敏感性。用Logistic映射产生的混沌序列通过排序来改变图像中各像素点的位置, 达到混淆的目的, 在此基础上, 应用Chen混沌系统对Logistic加密的结果通过改变各点的像素值再进行加密。由于混沌系统所独有的特性, 使得双重加密的结果更加安全。

2 加密算法

2.1 应用Logistic映射进行加密

Logistic映射的表达式如 (1) 所示, 它是一个典型的混沌映射。

其中Xn∈[0, 1], 当参数b取值范围为 (3.569, 4]时, 系统具有混沌特性。

一般用它产生的混沌序列直接对信息进行加密, 但是在计算机有限的精度下, Logistic映射进行迭代的结果会出现重复, 这会给密码分析者带来攻击的机会。如在3位有效数字下, 其有一个13个值的循环, (0.109, 0.338, 0.950, 0.190, 0.610, 0.946, 0.204, 0.650, 0.910, 0.328, 0.882, 0.416, 0.972, 0.109) 。如果把Logistic映射产生的双精度序列进行一下排序, 进而对图像的各像素点位置进行排序, 以此来达到置换像素点位置的目的, 就可以避免重复所带来的不安全性。

用MATLAB进行仿真实验, 其步骤如下:

a.选取一个M×N的灰度图像。

b.给定参数b值和Logistic映射的初值x0, 让系统迭代M×N次, 产生M×N个值, 并对其进行排序。

c.把图像的二维顺序按照先行后列的顺序变成一维顺序, 并根据步骤b最后的顺序相应的对图像进行排序。

d.恢复步骤c为二维图像, 即为加密之后的图像。

经过Logistic映射加密之后的图像已经达到了图像混乱的目的, 但是并没有改变原始图像中各像素点的像素值, 为了增加系统的安全性, 将加密后的图像再送入Chen混沌系统, 改变各像素点的值。

2.2 应用Chen混沌映射进行加密

Chen混沌系统的表达式如 (2) 所示, 它也是一个典型的混沌系统。

其中 (x, y, z) 为系统轨迹; (a, b, c) 为系统参数。当a=35, b=3, c=28时, 系统有一个奇怪吸引子, 处于混沌状态。Chen混沌系统的参数更多, 相对也更安全。用此系统对Logistic映射加密后的图像再进行加密的步骤如下:

a.给定Chen的初值x0, y0, z0, 让系统迭代M×N次。

b.将每次产生的三个序列值按照公式 (3) 进行计算:

其中函数fra是求三个序列平均值的小数部分;计算机的有限精度是15位, 小数最多占用14位, 所以将其放大1014使之变成正整数;图像的灰度值是在 (0-255) 之间, 所以将放大的正整数对256求余, 使结果也在 (0-255) 这个区间。

c.将Ki转化成二进制;将第一次加密产生的图像的各像素点的值也转化成二进制, 并将Ki与其逐个进行异或处理, 共M×N次。

d.将M×N个结果再转化成十进制, 变回二维图像, 完成第二次加密。

这样, 图象中各点的位置和像素点的值都发生了变化, 从而达到了混乱和扩散的要求, 增加了加密的安全性。其安全性主要在于混沌系统对初值的极其敏感性, 系统的初值有一个微小的变化, 其混沌轨道会发生根本的变化, 即所谓的“蝴蝶效应”。为了验证算法的可行性, 我们通过实验来进行仿真分析。

3 仿真实验

选取一幅104×102的灰度图像, 令Logistic映射中的参数b=4, 初值X0=0.7, 则原始图像和第一次加密之后的图像如图1所示。

令Chen混沌系统的初始值x0=-9.036, y0=0.768, z0=29.263, 则第二次加密之后的图像如图2中 (a) 所示;用所有正确的初值进行解密图象如图2 (b) 所示。

从图1和图2中可以看出, 经过Logistic映射后, 已经把图象的各像素点的位置进行了重新的排序;经过Chen混沌系统后, 已经混乱的图象, 通过改变其像素值, 再次进行了加密。

经过大量的实验, 对两个混沌映射选择不同的参数值, 加密之后的图像效果都是“面目全非”的;选择不同的图像, 以及不同大小的图像都能得到同样的加密效果, 这说明用此方法起到了很好的加密作用。

为了验证加密算法的有效性, 可以对该方法进行安全性分析。

4 安全性分析

4.1 密钥量分析

采用Logistic映射和Chen混沌系统进行双重加密的关键技术就是混沌系统本身的初值敏感性。如果我们将Logistic映射的初值x0和Chen混沌系统的初值x0, y0, z0都进行保密, 把他们当作密钥来处理, 按照计算机的双精度来计算, 密钥量可以达到1060, 可见整个系统的密钥空间是很大的。

4.2 敏感性分析

既然混沌加密的安全性就在于它的初始值敏感性, 那么当截获者对得到的密文图像进行破解时, 如果针对两次加密的初始值有一点点偏差的情况下, 也不能还原出原始图像。图3 (a) 是对两次加密的图像图2 (a) 用x0=-9.036, y0=0.768, z0=29.263000001进行解密的图像。我们看到初始值z0仅仅和原来有微小的差异, 可是却没有还原到图1 (b) 的状态;图3 (b) 是针对图1 (b) 用X0=0.700001进行解密的图像, 同样是小的差异, 也没有还原出原始的图像。按照十进制小数双精度为15位来进行穷举攻击, 对4个参数的攻击难度也将达到1060, 所以用穷举法进行攻击显然是不行的。

4.3 统计分析

该加密方法已经改变了图像各点的像素值, 即加密后图像的灰度直方图也发生了变化, 图4是原始图像的灰度直方图, 图5是加密后图像的灰度直方图。从图中可以看出, 原始图像的像素值在某些点出现的频率很高, 比如像素值为100左右和210左右, 而加密后的直方图呈现正态分布。攻击者通过像素值出现频率的大小来破解显然是困难的, 这样就可以有效抵抗用统计方法进行的攻击。

4.4 时间复杂度分析

本算法中, 生成混沌序列主要是通过迭代, 若问题的规模为m, 则生成混沌序列的时间复杂度为O (m) 。为线性阶的时间复杂度, 而且时间复杂度较低。为检测算法的时间开销, 对不同大小的8位和24位BMP位图进行了大量的加解密实验。实验所采用的硬件系统是Pentium42.8G CPU, 512M DDR内存;软件系统为WindowsXP操作系统, MATLAB编程平台。在实验中, 对数据大小为2.25M的1024×768的24位BMP图像加密所用的时间约为0.38s, 解密所用的时间约为0.42s。该速度可以满足要求, 可见算法的效率较高。

4.5 空间复杂度分析

算法主要空间开销是保存混沌序列所使用的4个1维数组, 每个数组大小等于图像像素数。若待加密图像大小为M×N, 采用int型数组, 则总的大小为M×N×4个int型空间。可见空间开销只与图像大小有关, 与图像位数无关。例如, 对一幅1024×768的图像, 其空间开销约为1024×768×4/ (1024×1024) ≈3M。若问题规模为m, 则算法空间复杂度为O (m) 。

4.6 图像处理攻击分析

若加密图像被攻击者进行恶意破坏, 如加噪、滤波、剪切等图像操作, 测试结果表明:对加密图像轻微剪切并不影响图像解密操作。图6 (a) 是对加密图像剪切掉12.5%的图像, 图6 (b) 是相应解密图像;图6 (c) 是对加密图像剪切掉25%的图像, 图6 (d) 是相应解密图像。可见剪切12.5%对图像的恢复没有太大影响, 即便剪切掉25%, 也可清晰的看到原始图像轮廓。所以, 该方法可抵抗一定程度的剪切攻击。实验显示, 对加噪和滤波等图像处理攻击也有一定抗干扰能力。

5 结论

把混沌理论和密码学相结合是最近几年的事情, 但是已经显示出很强的发展趋势。Logistic映射和Chen映射都是典型的混沌映射, 本文利用混沌映射具有的初值敏感性对原始图像进行了双重加密。通过实验分析发现, 加密之后的图像满足了混淆和扩散, 不仅改变了像素点的位置, 还改变了像素点的值;具有密钥量大、抗初值攻击、抗统计和抗图像处理攻击等优点, 从而增加了系统的安全性。当然还有很多需要改进的地方, 如何选择一个好的混沌映射一直是人们所关心的问题。

参考文献

[1]Kocarev L.“Chaos-based cryptography:a brief overview.”IEEE Circ System Magzine, vol.1, no.3, pp.6-21, 2001.

[2]Chen G R, Mao Y B and Chui C K.“A symmetric image encryption scheme based on 3D chaotic cat maps”.Chaos, Solitons and Fractals, vol.21, pp.749-761, 2004.

[3]Kocarev L, Jakimovski G.“Chaos and cryptography:from chaotic maps to encryption algorithms”.IEEE Trans Circ System-I, vol.48, no.2, pp.163-169, 2001.

[4]Yen J C, Guo J I.“A new chaotic key-based design for image encryption anddecryption.”Proc IEEE Int Conference Circuits and Systems, vol.4, pp.49-52, 2000.

[5]Scharinger J.“Fast encryption of image data using chaotic kolmogorov flows.”Electron Imageing, vol.7, no.2, pp.318-325, 1998.

[6]Zhi-Hong Guan, Fangjun Huang and Wenjie Guan.“Chaos-based image encryption algorithm.”Physics Letters A346, pp.153-157, 2005.

映射算法 篇4

关键词：光子映射,均匀网格,GPU,偏移表

0 引言

光子映射是全局光照算法,通常先从光源向场景发射光子,建立基于K-D tree的光子图,接着从光子图中寻找估算点的光子完成对估算点光辐射强度估算,最后生成图形[1]。光子映射的光子图与场景表述可以分离,光子映射能处理很复杂的场景,包括千万个三角面片、实例化的几何体、复杂的过程式物体[2]。

针对通常算法消耗内存大、生成图形慢的缺点,Per H Christensen[3]于2002年提出凸多边形的思路,该方法是获取一组离估算点最近的光子,再求出包围光子的最小凸多边形,进而利用凸边形的面积作为估算光辐射强度估算时的分母。该方法能比较精确地估算光辐射强度,但耗时很长。同年Heinrich Hey[4]提出另一种精确估算光辐射强度的算法。该算法的思想是:场景中的每个物体都用网格表示出来,采用立方体收集光子,并求出每个立方体内的多边形面积,每个光子的能量平均分配到光子正对着的多边形,每个多边形的光辐射能应与沿着光子入射方向的投影面积成正比。2005年Szbolcs Czuczou[5]应用图形硬件的纹理结构存储光子,用滤波方式搜索最邻近的光子信息,该方法的好处是可以一步获取所有顶点的辐射能,缺点是获取的辐射能仅是平均值。2008年Hachisuka等[6]采用逐步缩小估算半径,同时采用加大光子密度的办法,在渲染水面焦散时效果较好。2009年Dan A.Alcantara[7]等在GPU上实现光子的哈希并行算法,搜索有效光子的速度更快,但需开辟较大的共享内存。耿中元、徐庆为[8]为了改善物体细节部分的绘制效果,2009年提出对搜索范围内的每个光子都求出它在绘制点上的切平面投影,通过判断投影点与绘制点之间的距离是否小于搜索半径,进而决定是否使用该光子计算光辐射强度。2011年Wojciech Jarosz[9]等提出采用自适应光子束方法渲染有参与介质的柱状型光照时取得较好效果。2012年Doidge[10]结合渐进光子映射算法与路径跟踪算法的优点,在渲染焦散现象时采取光子映射算法,渲染其它现象时则采用光线跟踪算法,两种算法互相切换的花费较大。2013年Ben Spencer[11]等先为每个光子划分一个沃罗诺伊空间,接着采用渐进光子的方式计算光辐射强度。2013年Mara、Luebke、McGuire[12]利用GPU的栅格硬件,在对光辐射强度估算时采用多面体方法获取光子,提高了光辐射强度的精度,先从理论上证明该方法的一致性,实验上也验证了该算法的有效性,但该算法在处理较复杂的场景时会对估算点重复计算。

新算法先将物理空间分成均匀网格,然后发射光子,再建立均匀网格与光子的映射关系偏移表,实验结果比通常基于K-D tree的光子映射算法更快,图像也更清晰。

1 网格算法

Step1:空间均匀网格建立。先将场景分为可与图形像素一样多的包围盒[13,14],之后再根据统一的尺寸划分网格,一般网格以搜索半径r[15]为长度。划分网格时间只占整个网格构建的一小部分时间。

Step2:为每个光子计算索引。网格建好后需要为每个光子分配光子索引可采用如下方式分配索引:

其中,G(p)=[(p-worldOrigo)/cellSize]。GridSi-zex表示x轴上的网格数,GridSizey表示y轴上的网格数,GridSizez表示z轴上的网格数。索引值的范围为0~N,其中N=GridSizex.GridSizey.GridSizez.所有的光子都分配到0~N-1中去,由于这部分可以并行进行,采用GPU的kuda作并行计算[16,17]。

Step3:偏移表(Offset Table)计算。完成均匀网格划分、光子存储、光子与网格对应关系建立,再建光子偏移表,用于光子搜索,如图1所示。

Step4:利用均匀网格寻找光子。利用存储光子的数组和偏移表,查找估算点的光子,如图2所示,需要寻找到所有符合要求的光子。先找到估算点要达到的最小网格和最大网格,如在x轴的最小网格和最大网格半径内,如果网格空间的大小正好等于搜寻半径,则在立体空间中最多需要搜寻8个网格,可用GPU的kuda并行搜寻。算法描述如下:

2 结果分析

实验条件:系统Win7,处理器Intel I5处理器2.5G,内存8G,Geforce 610,使用C++GL渲染图形。在网格划分好后,使用GPU的cuda技术,场景1为像素640×480,发射的光子数为50 000个;场景2像素为1 366×768,发射的光子数为100 000;场景3像素1 366×768,发射的光子数为200 000个。从图形清晰度来看,网格算法的清晰度比K-D tree算法清晰度更高,原因是网格算法建立光子的映射关系更精准。从表1、表2、表3可以看出,在各场景中网格的构建时间比kd树的构建时间都快,最大内存消耗网格算法比K-D tree算法低,在总的渲染时间上,网格算法比K-D tree算法低。

3 结语

新的算法是先将空间划分成均匀网格,发射光子后,再利用GPU的并行功能建立光子与网格映射光子,最后利用该映射关系来查找估算点的光子,进而渲染图形。在以后的研究中可以更多地利用GPU并行功能加速图形的生成,并进一步优化光子与网格的映射。

映射算法 篇5

关键词：本体映射,一对多映射,概念属性

1 概述

本体作为一种领域知识概念化和模型化的方法已经获得广泛认可。本体映射是为了实现不同数据源的数据之间的通信，它是数据共享的核心技术，在数据仓库，集成系统，P2P等中都有广泛的运用。当今，大量的工作集中于在不同的Ontology中发现1-1映射。如何构造复杂的映射(多对多)则是本体映射研究领域中一个新的难点。实现多对多映射的主要挑战在于，如何构造和筛选候选映射集，即对于一个目标概念，如何选择与之映射的候选概念的个数。本文将基于概念的属性，研究一对多概念相似度计算方法。

2 相似度计算

根据Gruber定义了一个典型的本体由五元组表示[1]：O=(C,I,R,F,A)。其中，C代表概念集合;I表示概念的实例;R为定义在概念集合上的关系集合;F为定义在概念集合上的函数集合;A表示公理集合。

现在大部分的对于两两概念相似度的研究主要从以下四个方面入手：概念名称相似度、概念属性相似度、概念实例相似度，以及概念关系相似度。比如在Halevy教授等开发的GLUE[2]，IMAP[3]系统是从概念的实例出发，引入机器学习的办法，从而发现本体间的映射。

本文基于概念属性的相似度计算的理论依据是：如果两个概念的属性都相同，则这两个概念是相同的;如果两个概念具有相似的属性，则这两个概念也是相似的。

2.1 两两属性相似度计算

大部分概念属性的研究，即比配两个属性的相似度，从属性的名称入手，考虑名称的差异性和语意关系。

首先，考虑名称的差异性。引入由Levenshtein提出的编辑距离[4]。编辑距离是一个用来衡量两个字符串差别的方法。它用一个动态规划算法计算把一个字符串转换成另一个字符串，所需要对字符进行的最小操作数，包括对字符的插入、删除、替换。计算公式如下：

其中，simdis(e1,e2)表示两概念属性之间的编辑距离相似度，e1和e2分别表示本体O1和O2中两个概念的属性，dist(e1,e2)表示两个字符串的编辑距离。

其次，考虑两个词之间的语意关系。因此引入WordNet，根据Lin提出的利用概率的方法计算两个概念属性的相似度[5]。计算公式如下：

其中，simwn(e1,e2)表示两属性利用WordNet得到的相似度。其中p(s)=count(s)/total，表示WordNet中词义节点s及其子节点所包含的单词个数在整个辞典中所占的比例，total是WordNet的单词总数。另外e1∈s1,e2∈s2表示单词e1和e2分别位于WordNet节点s1和s2中。节点s是s1和s2的公共祖先节点。

综合以上的分析，我们得到最后的两两属性相似度公式：

其中,w1,w2∈[0,1],w1+w2=1。

2.2 两两概念相似度计算

从单方向考虑，对于目标概念，如何在另一个本体中找到与其最比配的概念。当然，更一般的作法，需要双向的计算。这里为了方便阐述，只考虑单方向。

根据先前理论依据的描述，为了实现在另一个本体中查找出一个概念，使这个概念的属性与目标概念的属性比配度最高。

假设要计算A和B两个概念的相似度时，假设A有m个属性a1…am，根据如下公式计算A,B的相似度：

其中wi表示对A中的每个属性分配个权重，bj为概念B中的某个属性。

这里有两个问题需要展开：选概念的查找，有很多问题涉及对候选集合的筛选，如利用兄弟节点相似的规则，减少搜索的空间;对A中每个属性权重的分配，根据信息熵，对每个属性进行排列，从而得到各个属性的重要性，进而进行权重的分配。

2.3 一对多概念相似度计算

根据以上两两概念间的相似度计算式，我们进行扩张，提出了一对多的概念计算公式，该公式如下：

其中A代表某个概念，其包含属性a1…am。wi表示对A中的每个属性分配个权重。与(4)公式不同的是：式中的C不在是代表某个概念，而是代表概念的集合。同理cj代表概念集合中某个概念的属性。

3 一对多映射算法

对于两个Ontology(假设一个为源本体S，一个目标本体T)，我们要实现S到T的映射。但一般的做法，我们同时还需要完成T到S的映射。

一对多映射中主要的问题在于概念候选集是个无穷的集合。我们在此引用集束搜索(beam search)算法。对每个目标概念，具体步骤如下：

Step1：对某个目标概念，都生产1-1映射，并根据公式(4)计算其相似度。

Step2：运用beam search算法。该算法的主要思想是：对上一步(假设上一步为第i步，其映射为1-i映射)计算出来的相似度进行从高到低排列，选择最大的K个映射，然后对这K个映射进行概念的添加，且每次只添加一个概念，这样就生成了1-(i+1)映射，并根据公式(5)计算其相似度。重复第2步，直到收敛。

这里需要说明两个问题：

1)迭代终止条件，我们采用与IMAP系统相似的终止条件：当这轮候选集的最大相似度与上一轮的最大相似度差值小于预先定义的一个阀值时，终止迭代，否则进行下一轮的映射计算。

2)概念的添加。在概念的添加中涉及到一个问题，即概念的组合方式。正如第一章中所引用的例子，有些概念只需单单的连接，但有些概念需要算术符的计算。本文只把连接方式引入到系统当中。

下面通过一个简单例子阐述我们的思想。假设在目标本体T中有概念DATE，其包含的属性有year,month,day，简写为DATE(year,month,day)。源本体S中有两个概念为DATE1(month,day)和DATE2(year)。可以看出，如果单单是实现1-1映射，无论是S:DATE1还是S:DATE2都不能很好的与T:DATA实现映射。

但如果引入以上算法，具体步骤如下：对于目标概念DATE，先考虑所有的1-1映射，其候选映射包括了T:DATE--S:DATE1,T DATE--S:DATE2等等。然后根据公式(2.4)计算以上所有1-1映射的相似度。之后运用集束搜索，对1-1映射的结果进行从高到低的排序，选取最高的K个1-1映射，进行概念添加。如我们选取了T:DATE--S:DATE1，接着从源本体中选择概念进行添加，进而生成1-2映射，如T:DATE--concat(S:DATE1,S:DATE2)等等。对于1-2映射，我们根据公式(5)计算其相似度。如此循环，直至收敛。

4 结束语

本体匹配是解决本体异构问题的主要方法。目前的研究多集中于发现概念间的一对一映射，但更为普遍的应用，需要我们挖掘出概念间多对多的映射。针对这个问题，本文提出了一种实现一对多的本体映射方法。在一对一概念映射的基础上，提出了一对多概念相似度计算公式，在候选集查找方面，引入集束搜索减少概念映射候选集合空间，该方法能够较好的发现本体中一对多的概念映射。

参考文献

[1]Gruber T R.A Translation Approach to Portable Ontologies[J].Knowledge Acquisition,1993,5(2):199-201.

[2]AnHai Doan,Jayant Madhavan,Robin Dhamankar,Pedro Domingos,Alon Halevy.Learning to match ontologies on the Semantic Web[J].VLDB Journal,2003(12):303-319.

[3]Robin Dhamankar,Yoonkyong Lee,AnHai Doan,Alon Halevy,Pedro Domingos.iMAP:Discovering Complex Semantic Matches be-tween Database Schemas[C].In SIGMOD'04,2004:383-394.

[4]Levenshtein V I.Binary Codes Capable of Correcting Deletions,Insertions,and Reversals[J].Cybernetics and Control Theory,1966.

映射算法 篇6

网络地址转换 (Network AddressTranslation, NAT) [1,2]技术解决了在网络上的主机和Internet之间提供IP层访问的普遍性问题, 不需要网络上的每台主机都有一个全球有效的IP地址。NAT技术通过将局域网上的主机地址映射为Internet上的合法IP地址, 从而实现网络地址复用。由于NAT技术不仅可以隐藏内部网络地址信息, 使外界无法直接访问内部网络设备, 保护了内部网络, 同时NAT也帮助暂时解决IPv4地址分配的限制。但是随着基于Internet的P2P网络技术的广泛应用, 更多的内网主机需要参与到P2P中来。NAT之后的主机IP地址在Internet上是不可见的, Internet上的主机不能主动访问这些NAT之后的主机, 而位于不同NAT之后的主机间更是无法相互识别而不能直接交换信息。但是P2P网络要求任何主机之间都能够直接对等交换信息, 这就使得P2P网络应用必须解决穿越NAT实现双向对等通讯的问题。采用UDPHole Punching技术以实现NAT的穿越, 即通过一台Internet上的注册服务器, 利用UDP (UserDatagram Protocol) 穿越NAT的方式实现P2P网络中双向对等通讯;同时, 提出一种自适应算法, 使得NAT之后的主机能够按照算法的策略向NAT发送保持映射的UDP消息, 解决了NAT中动态端口地址映射失效的问题。

1 NAT与P 2P

1.1 NAT概述

NAT通过将局域网上的主机地址映射为Internet上的合法IP地址, 从而实现网络地址复用。这一功能很好地解决了公共IP地址紧缺的问题。简单的说, 它是一种把内部私有IP地址翻译成合法网络IP地址的技术。现在应用最为广泛的NAT类型是NAPT, 几乎所有的NAT设备都支持NAPT。

1.2 NAPT实现原理

NAPT (NetworkAddressPortTranslator) [3]使得一组主机可以共享唯一的公用IP地址, 当位于内部网络中的主机通过NAT设备向外部主机发起会话请求时, NAT设备就会查询NAT映射表, 看是否有相关会话记录, 如果有相关记录, 就会将内部IP地址及端口同时进行转换, 再转发出去;如果没有相关记录, 进行IP地址和端口转换的同时, 还会在NAT映射表增加一条该会话的记录。外部主机接收到数据包后, 用接收到的合法公网IP地址及端口作为目的IP地址及端口来响应, NAT设备接收到外部回来的数据包, 再根据NAT映射表中的记录把目的地址及端口转换成对应的内部IP地址及端口, 转发给该内部主机。

假设有一个私有网络192.168.1.*, Client A是其中的一台计算机, IP地址为192.168.1.5, 这个网络的网关 (一个NAT设备) 的外网IP是222.76.76.230, 内网的IP地址为192.168.1.1。如果Client A中的某个进程创建了一个UDP Socket, 这个Socket绑定1234端口, 而这个进程想访问外网主机179.16.62.2的1235端口, 那么当数据包通过NAT时, NAT会改变这个数据包的原IP地址, 改为222.76.76.230。接着NAT会为这个传输创建一个Session并且给这个Session随机分配一个端口, 比如9900, 然后改变这个数据包的源端口为9900。所以本来是 (192.168.1.5:1 234→179.16.62.2: 1235) 的数据包到了Internet上变成了 (222.76.76.230:9900→179.16.62.2:1 235) 。 一旦NAT创建了一个Session后, NAT会记住此次动态地址转换的映射记录, 以后从179.16.62.2发送到9900端口的数据会被NAT自动的转发到192.168.1.5的端口1234上。当然NAT的9900端口只会转发从179.16.62.2发来的数据包, 其他的IP发送到这个端口的数据将被NAT抛弃, 这样Client A就与Server建立了一个连接。但是这个连接能保持多久呢, 也就是说这条动态地址映射记录能保持多久呢?也许是几分钟, 也许是几小时, 这要看具体的实现了。所以这里有个动态端口地址映射的失效问题。

1.3NAT阻碍P2P应用

NAT技术在缓解IPv4地址紧缺问题、构建防火墙、保证网络安全等方面都发挥了重要作用。然而NAT设备的广泛存在却给Internet上的主机, 特别是处于不同内网中的主机进行P2P通信带来了障碍, 限制了P2P的应用。通过NAT上网时, 只能由NAT内的计算机主动向外部的主机发起连接请求, 禁止外部主机主动与NAT内部主机建立连接。如对于采用P2P方式的下载程序而言, 由于NAT内的计算机不能接收NAT外部的连接, 从而导致连接数目过少, 下载速度慢。因此P2P软件必须解决NAT的内部主机不能被外部连接的问题。

1.4UDP穿越NAT技术

现阶段UDP穿透NAT的方法已经比较成熟, 大多采取UDP Hole Punching技术[4,5]。

UDP Hole Punching的主要思想是:通过在Internet上部署一台注册服务器, 任何主机都要先登录到注册服务器, 注册服务器从接收到的UDP 数据报头中提取IP 地址和端口信息, 存储并维护各客户端的地址和端口号信息。当双方需要通信时, 可以通过服务器的“介绍”获取对方的端点地址, 建立“直接”的连接。

图1是一个具有NAT设备的典型网络拓扑图, 其中C1, C2位于不同的私有网络中, 内网边界的路由器具有NAT的功能。C1与C2无法直接通信, 但都可以访问服务器。下面分析UDP Hole Punching的基本流程, 假设C1想访问C2, 当然事先C1和C2都已在服务器上注册了。

1) C1从服务器获取到C2的端点地址, 发送“刺探”消息, 因为NAT2上还没有相应的映射记录, 所以该数据包被抛弃;但这时却在NAT1上记录了C1到C2的映射记录, 即打通了C1和C2之间的NAT1。

2) C1向服务器发送消息请求, 要求服务器向C2发送消息 (因为在C2登录服务器时, 已经打通了C2和服务器之间的NAT, 所以服务器能够访问得到C2) , 告诉C2向C1的端点地址发送“刺探”消息。

3) C2收到服务器发来的消息后, 向C1的端点地址发送“刺探”消息, 这时打通了C1和C2之间的NAT2, 而在1) 中也打通了C1和C2之间的NAT1, 所以这时C1就可以收到C2发来的“刺探”消息, 故C1知道此时已经建立了与C2的“直接”连接。至此, 双方建立可以互通的连接。

在这里应该考虑在节1.2里提到的动态端口地址映射的失效问题。因为UDP是无连接的协议, NAT对UDP传输的映射是动态的, 也就是说经过一段时间之后, 如果内网主机不再发送或接收数据, 映射后的 (IP地址:端口号) 会发生改变, 映射关系会自动解除, 端口号会被NAT收回, 重新分配给其他连接。这样在注册服务器上的映射表就会变得无效, 主机也就不能为其他主机所识别。所以必须保证注册服务器能够访问到各NAT后的主机, 如果不同NAT后的主机之间的连接失效, 还可以通过注册服务器“介绍”重新建立连接。

为了保证注册服务器能够访问到各NAT后的主机, 提出一种NAT端口映射保持的自适应算法, 让NAT后的主机能够按照算法的策略向NAT发送保持映射的UDP消息, 保证NAT为相应主机分配的UDP端口不被删除。

2NAT端口映射保持的自适应算法

算法的主要思想是NAT后的主机按照动态的时间间隔向NAT发送冗余的UDP数据包, 发送的目的地址是该主机登录注册服务器时, NAT为它分配的Internet合法IP地址和相应的UDP端口。由于UDP的无连接性, 任何主机发送到该Internet合法IP地址和UDP端口的消息, 经过NAT后消息都将被相应的内网主机所接收到, 所以此时相当于主机本身向自己发送了一条UDP消息, 主机接收到这样的消息后直接丢弃, 这样, 映射关系就能够保持。具体的过程如下。

启动期:各NAT后的客户端主机登录服务器注册映射的公网端点地址, 该注册地址是服务器通过解析客户端数据包观察到的。现在假设NAT的内网地址为192.168.1.1, 外网地址为222.76.76.230, 内网中的一台主机A的IP地址为192.168.1.5, 端口为1234, 注册服务器的IP地址为202.200.146.5, 端口为8000。当主机A注册后, NAT将动态分配222.76.76.230的一个端口给A, 假设为9900, 即映射关系为: (192.168.1.5:1234→222.76.76.230:9900) 。注册服务器上保存主机A的公网端点地址 (222.76.76.230:9900) 。现在内网主机A发送保持映射消息 (SRC:192.168.1.5:1234, DST:222.76.76.230:9900) , 则经过NAT后消息将被主机A (192.168.1.5:1234) 所接收到并丢弃, 但是这却保证了映射关系不被删除。

增长期:客户端以Tspan (k) (Tspan (k) = (2k-1) t0, t0是一个单位时间, 取t0<5 (min) , k代表当前第几次发送) 间隔向NAT (如上面的主机A, 发送UDP消息的目的地址为222.76.76.230:9900) 发送冗余数据包, 保持源端点地址在NAT设备上的活动;当T′> C (T′= Tspan (i) > C, C代表阈值, 小于设备映射保持的平均时间, 取C<30 (min) ) 时, 以后的间隔时间段采用按秒递增的形式微调, 即Tspan (k) = T′+ k。

波动期:当NAT后的主机收不到自己发出的冗余数据包时, 重新登录注册服务器注册, 之后客户端根据最后一次的间隔的二分之一发送冗余数据包, 即T′span=Tlast/2。后续的间隔时间段按照增长期的过程增长。

上述过程, 充分考虑了NAT设备的本身映射有效保持时间的一般特性, 使得客户端都能够自适应网络情况调整最佳的间隔时间, 向NAT发送映射保持的UDP消息, 确保了注册服务器能够访问到各NAT后的主机, 从而解决了NAT阻碍P2P网络应用的问题。

3结束语

提出了一种NAT端口映射保持的自适应算法, 让NAT后的主机自适应网络情况调整最佳的间隔时间主动向NAT发送冗余UDP数据包, 保证NAT中的端口地址映射不被删除。NAT的存在, 使得外网主机无法穿过NAT主动与内网主机进行通信, P2P网络各主机无法彼此发现对方进行对等信息交换, 特别是位于不同NAT之后的不同内网中的机器, 更是无法相互连接。那么P2P网络应用就不得不考虑NAT穿越, 而NAT穿越又不得不考虑NAT端口地址映射的失效问题, 所以该算法会对P2P网络技术的广泛应用起到积极作用。

摘要：通过对NAT的原理分析, 对位于NAT设备后的两个内网主机之间相互通信的问题提出了解决方法。分析了UDP穿透NAT的基本原理后, 给出了简单健壮性很好的UDP Hole Punching技术以实现NAT的穿越。最后提出一种NAT端口映射保持的自适应算法, 解决了NAT中动态端口地址映射的保持问题。

关键词：点对点,网络地址转换,用户数据包协议,NAT地址映射

参考文献

[1]谢希仁.计算机网络 (第四版) .北京:电子工业出版社, 2005

[2]汪小帆, 李翔, 陈关荣.复杂网络理论及其应用.北京:清华大学出版社, 2006

[3]徐勤军.P2P穿透NAT原理浅析.漳州师范学院学报 (自然科学版) , 2008;3 (61) :51—55

[4]招俏春, 李榕.P2P网络传输中NAT穿越的研究.电力系统通信, 2008;29 (189) :60—64

k-匿名映射的一种局部搜索算法 篇7

可用的共享数据, 是进行科学分析与研究的重要资源, 然而, 每一类数据背后都会包含着一些敏感的隐私信息。无论这些数据的发布范围局限在什么程度, 一个首先必须解决的问题是如何保护那些隐私。

广泛使用的美国人口普查数据就是这样的一类共享的数据资源。尽管数据发布时, 个人姓名、社会保险号等标识性 (ID) 信息已被消除, 只余下年龄、性别、种族、文化程度、婚姻状况等准标识 (QID) 信息以及职业和收入等敏感 (SA) 信息, 但第三方依然可以利用其他的共享数据资源 (如公布的选民资料数据) , 由QID信息准确推导出某个特定个人的 (SA) 信息。为抵御这类链接攻击, 人们提出了k-匿名技术来处理对待发布的数据[1]。

k-匿名的基本想法是将原始数据中的每个QID的具体值映射 (k-匿名映射) 成一个通用值, 使得处理后的数据中具有相同QID向量值的元组数至少有k个, 从而将链接攻击成功的概率降为1/k, k-匿名处理会带来数据可分辨度的降低, 减少数据可用性。因此, 寻求隐私保护度和数据可用性的折中, 是构造k-匿名映射的重要原则。

已有的研究表明, 构造k-匿名映射的复杂度与QID属性的个数存在密切的关联性, 寻求具有最佳可用性的k-匿名映射的问题是NP困难的[2]。即使QID属性个数有限, 如果待处理的数据量大, 构造具有最佳可用性的k-匿名映射也需要消耗大量的计算资源[3]。

局部搜索算法是一类寻找最优解的近似算法, 它从一个初始解开始, 每一步在当前邻域内找到一个更好的解, 使目标函数逐步优化, 直到不能进一步改进为止。依据局部搜索原理, 如果我们能够快速找到一个可行的k-匿名映射, 就有可能通过逐个属性的搜索, 优化这个映射以获得较佳的可用性。

1基本概念

1.1泛化映射及映射深度

考虑一个关系表T[Q1, Q2, …, Qn , S1, S2, …, Sm], 其中QIT = {Q1, Q2, …, Qn }为准标识属性集, SAT = {S1, S2, …, Sm }为敏感属性集。

定义1 k-匿名[1] 关系表T满足k-匿名, 当且仅当T[QIT]中的每条记录重复出现至少k次。

定义2 泛化映射 映射f:X→Y称为一个泛化映射, 若f (A) =a, 其中A⊆X, a∈Y。

泛化映射的构造依赖于一个预定的概念层次, 层次的最高端代表最通用的概念, 用“*”表示, 而最低层则为最具体的概念, 即原始数据的值。特别的, 约定恒等映射f:X→X为一类特殊的泛化映射记为f0, 而当所有X中的值被映射为*时, 记这个映射为f*:X→*。

给定一个QID属性Q及其上的泛化映射f, 若属性值q∈T[Q], 集合E (f, q) ={x| f (x) = f (q) , x∈T[Q]}称为q在映射f下的等价类的集合。称f= (f1, f2, …, fn) 为QIT上的一个泛化映射向量, 其中fi为属性Qi的泛化映射, i = 1, 2, …, n。给定QID属性向量q= (q1, q2, …, qn) 和一个泛化映射向量f= (f1, f2, …, fn) , 记 f (q) 为向量 (f1 (q1) , f2 (q2) , …, fn (qn) ) , 集合E (f, q) ={x| f (x) = f (q) , x∈T.QID}称为q在映射向量f下的等价类的集合, 于是T[QIT]可以看作是由一系列不同的等价类构成的集合, 即T[QIT]=∪qE (f, q) , 其中当q1≠q2时, E (f, q1) ∩E (f, q2) =ϕ。此时, 若|E (f, q) |代表对应的等价类的个数, 则DM (f) =∑q|E (f, q) |2为度量可用性的可分辨度量[3]。

定义3 泛化映射的序 设f1:X→Y1, f2:X→Y2是两个泛化映射, 若存在Y1→Y2的泛化映射, 则称f1先于f2, 记作f1<Df2。

对于:满足f1<Df2的两个泛化映射f1、f2, 若不存在f3使得f1<Df3且f3<Df2, 则称f1到f2的距离为1。称泛化映射fd的深度为d, 若存在d-1个彼此之间距离为1的映射f1, f2, …, fd-1, 满足f0<Df1<Df2<D...<Dfd-1<Dfd。当某个属性的泛化映射深度相同时, 称这个属性被等深泛化。

1.2一个具体的例子

表1显示了一个包含有四个属性的人口统计数据, 其中Age、Sex、Race属于QID属性, Occupation属于SA属性。对所有的QID属性, 可以通过预定的概念层次, 构造相应的泛化映射。图1即为Age属性的一个泛化映射层次。

表2显示了图1中的数据在映射向量 (Age2, Sex0, Race*) 的作用下, 达到了2-匿名, 注意到, 映射向量中Age2是一个等深映射, 即Age属性的所有值都被映射到同一层次上, 但实际上, Age属性在非等深映射

$Age{2}^{\prime }=\{\begin{array}{l}Age120\le age\le 29\\ Age240\le age\le 49\end{array}$

的作用下, 映射后的数据元组也能达到2-匿名 (如表3所示) 。表2和表3所示的2-匿名数据的可分辨度量分别为18和12, 这意味着采用非等深的映射可能获得较佳的可用性。

1.3过泛化及映射分解

定义4 过泛化的映射 给定一个非标识属性Q, 若Q上的一个泛化映射使T[f (Q) ]满足k-匿名, 且使得T[f (Q) ]中至少一条记录重复出现至少2k次, 则这个泛化映射为过泛化的映射。

定义5 过泛化的映射向量 若一个泛化映射向量使关系表T[f (QIT) ]满足k-匿名, 且使得T[f (QIT) ]中至少一条记录重复出现至少2k次, 则这个泛化映射向量为过泛化的映射向量。

定义6 可分解的过泛化的映射 设f为QID属性Q上的一个过泛化映射, 等价类集E (f, q) 满足q∈T[Q]且| E (f, q) |≥2k, 若存在q1, q2∈E (f, q) 且f可以分解为f1和f2, 满足 E (f, q) =E (f1, q1) ∪E (f2, q2) 且| E (f1, q1) |≥k, | E (f2, q2) |≥k, 则这个过泛化映射f称为可分解的过泛化映射。

定义7 可分解的过泛化的映射向量 设一个QID属性集合QIT上的一个过泛化映射向量f, E (f, q) 为f关于准标识属性向量q等价类且| E (f, q) |≥2k, 若存在q1, q2∈E (f, q) 且f可以分解为f1和f2, 满足E (f, q) =E (f1, q1) ∪E (f2, q2) 且| E (f1, q1) |≥k, | E (f2, q2) |≥k, 则这个过泛化映射向量f称为可分解的过泛化映射向量。

定理1 若f= (f1, f2, …, fn) 是T[QIT]上的一个过泛化的映射向量, 则至少存在一个i使得fi是一个过泛化的映射。

定理2 若f= (f1, f2, …, fn) 是T[QIT]上的一个可分解的过泛化的映射向量, 则至少存在一个i使得fi是一个可分解的过泛化的映射。

定理3 分解一个可分解的过泛化的映射向量, 可以减少匿名表的可分辨度量值。

2满足k-匿名的泛化映射的局部搜索

依据1.3节中的定理, 考虑这样的一个局部搜索过程, 由一个可快速构造的满足k-匿名要求的等深映射向量出发, 依据预定义的属性次序, 搜索并分解可分解的过泛化的属性映射, 形成新的非等深的可用性提高的映射向量。

Input:an integer k, a dataset, an attribute sequence attr_seq

Output: a mapping vector f that satisfied k-anonymization

procedure mainprocedure ()

find a mapping vector f on dataset satisfied k-anonymization;

repeat pick a∈attr_seq in sequence

if fa is over-generalized

reconstruct (k, a, f) ;

endif

until f is not over-generalized or all over-generalized maps cannot reconstruct

endprocedure

procedure reconstruct (k, a, f)

for each v∈T (QIT)

if |E (fa, va) |≥2k

find a split of fa on E (fa, va) s.t.|E (f1, v) |≥k∧|E (f2, v) |≥k

if found

updated f according to the split

endif

endif

endfor

endprocedure

这个算法首先寻找出一个满足k-匿名要求的映射向量, 这个映射向量的构造可以基于等深的泛化映射搜索。给定的属性次序采用循环队列的形式表示, 每次, 从循环队列中选择一个属性进行处理。若这个属性的泛化映射是过泛化的, 算法将调用reconstruct () 过程, 搜索并分解过泛化的映射。这个属性选择与映射分解的过程将不断重复, 直到泛化映射向量是非过泛化的或所有的过泛化映射不能再分解为止。

一个简单的reconstruct () 过程可以采用折半分解的策略来实现。假设指针low和high分别指向过泛化的属性数据空间的上、下界, 记这个空间为[low, high], 指针mid用于标示备选切割点, 其计算公式为mid= (low+high) /2, 于是这个数据空间可以分解为左空间[low, mid]和右空间[mid+1, high], 然后分别判断这两个子空间中的数据集是否满足k-匿名, 若满足, 则mid为映射的可能分割点, 否则若左子空间不满足, 则mid指针向右移动, 即重新计算mid= (mid + high) /2;反之向左移动, 即重新计算mid= (low + mid) /2直到备选切割点与low或high重合。之后确认当这个属性空间按 [low, mid]和[mid+1, high]分解后, 映射向量f是否依然保持k-匿名, 若保持, 则完成f的更新, 否则放弃此分解, 转到对下一个属性的处理。

3实验与讨论

为验证所设计的方法, 我们利用文献[4]中的人口普查数据进行了实验, 这组数据包括七个属性共48842条记录, 基本描述如表4所示, 其中Age, Sex, Race, Education, Marital Status为QID属性, Occupation和Salary Class为SA标识。我们采用Incognito算法[5]来构造初始的满足k-匿名的等深泛化映射, reconstruct () 过程基于折半分解的策略, 预设的属性分解次序按Age→Sex→Race→Education→Marital Status。

实验硬件环境为HP ProLiant ML370, 编程环境为Java (1.6.0_04) +MS SQL Sever 2000。实验对象为Incognito产生的10个10-匿名泛化映射, 这10个映射具有最低的泛化深度, 即若任一用例的任一属性若减少泛化深度, 都将导致10-匿名的破坏。

实验的详细结果见表5。

我们主要关注可用性的提高状况及增加的额外时间开销。图2显示了分解前后可用性的变化情况。我们发现经过所设计的算法处理后, 数据的可用性都得到提高, 提高量由23%至90%不等, 可用性平均提高了52%。图3显示了算法的运行时间, 在我们的实验环境中, 增加的额外计算时间在1-5分钟之间, 考虑到所实现的等深映射搜索过程所消耗的运算时间约为33分钟, 可以认为, 所增加的额外运行时间是有限的。

属性的等深映射由于要求属性值泛化到相同深度的概念层次, 因此可以较快地搜索出所有的等深映射向量, Incognito算法正是这样的一类典型算法。但是, 由于数据分布的不均匀性, 等深映射后的泛化数据会出现过泛化的现象, 这导致等深映射产生的匿名数据的可用性不高, 另一方面, 在不同的应用环境下, 不同属性的可用性需求是不一样的, 我们在算法中所引入的属性选定次序, 可以反映属性可用性需求的重要性程度, 这使得算法可以产生尽可能满足应用需求的匿名数据。

4结论

本文提出一个构造泛化映射的局部搜索算法, 在快速获得满足k-匿名的等深泛化映射的基础上, 依序寻找并分解属性的过泛化映射, 构造新的非等深的满足k-匿名的泛化映射。新映射增加了等价类的个数, 同时, 由于新映射的构造过程是一个局部搜索过程, 这使得只需要增加少量的计算时间, 就可得到可用性更高的泛化映射。

参考文献

[1] Sweeney L.K-anonymity:A model for protecting privacy.International Journal on Uncertainty, Fuzziness, and Knowledge-based Systems, 2002, 10 (5) :557-570.

[2]Aggarwal G, Feder T, Kenthapadi K, et al.Anonymizing tables.Pro-ceedings of ICDT.2005:246-258.

[3] Bayardo R, Agrawal R.Data Privacy through Optimal k-Anonymization.Proceedings of ICDE05, 2005:217-228.

[4] http://archive.ics.uci.edu/ml/.