一种基于MapReduce可公开验证数据来源的水印算法

常耀辉　隋莉莉　汪传建

摘 要 本文基于公开验证数据来源的水印算法，采用MapReduce并行编程框架进行设计，并通过实验证明了该算法的正确性和有效性。

【关键词】地理数据 公有水印 水印完整性 MapReduce

1 问题提出

地理数据库是地理信息系统的基础，由于地理数据的加工涉及大量人力、物力和财力，人们提出各种地理数据水印算法对数据的拥有者进行保护。大多数水印算法都需要进行大量的空间计算以及空间变换，特别是当目标地理数据中地物数较多或者地物形状较复杂时，进行水印信息的嵌入和检测都会消耗大量时间。各类水印算法往往关注数据的保真性和鲁棒性，而对水印算法的高效率执行却很少涉及。随着全球空间数据集的急剧增长，如何既快又好的进行水印的嵌入与检测成为许多研究人员关注的问题。文献提出一种可公开验证数据来源的水印算法，但时间复杂度较高，本文针对水印算法的效率问题，尝试应用MapReduce架构来解决水印信息的嵌入和检测的时间效率问题。

2 研究基础

2.1 预备知识

定义1 地物（Polygon）：一个具有m个顶点的多边形地物Pi可以描述为Pi={pi1， pi2，… pij， pi（j+1）=pim}，（j=1，2，…m），其中pij对应地物Pi中第j个顶点的二维坐标（pijx，pijy）。对于任意一个地物Pi来说，包含的顶点个数是可变的，我们用变量li来度量。

定义2地理数据集（Dataset）：一个包含n个地物的地理数据集D可描述为D={R，P=}，其中R为参考坐标系，P=表示数据库中的n个地物。

定义3 签名信息（Signature）：一个长度为k的用户签名信息可描述为S={s1，s2， …， si， si+1=sk}，（i=1，2，…k），其中si表示一个比特位，即si={0|1}。

公式1计算地物中心点：对于任意地物Pi，中心点Pi的x，y坐标由如下公式得出

Oix= pijx，Oiy= pijy （1）

公式2计算地物标识符：对于任意地物Pi，其标示符FIDi由如下方式确定：

FIDi=msb（Oi，h）=msb（Oix，h）||msb（Oiy，h）（2）

其中msb（Oix，h），msb（Oiy，h）和分别表示选取点Oi的横坐标Oix和纵坐标Oiy的高位h，||表示字符连接操作。

2.2 可公开验证数据来源的水印算法思想

根据D中的n个地物信息{P1，P2，…，Pn }和长度为k的签名信息{s1，s2， …， sk}，通过对地物中的数据进行水印信息嵌入，生成一个包含n个二进制向量的集合V（v1，v2，…vn），其中vi（1<=i<=n）为一个二进制向量，与原数据集D中的一个地物Pi相对应。每一向量由向量标识和若干个比特位两部分组成，Vi中比特位长度和Pi的维数相同，其长度等于对应地物Pi中包含的顶点个数li。对于待验证的数据集D'，应用水印检测算法生成二进制向量集合V'，通过比较验证签名算法依次比较V和V'，如果相同则认为D'来源合法，否则不合法。

3 算法介绍

MapReduce是由Google提出的一种分布式并行编程框架，是云计算平台主流的数据处理模型。MapReduce的编程原理是基于“分而治之”的思想，MapReduce将复杂的并行计算过程抽象为两个函数：Mapper（映射）和Reducer（规约），其中Map阶段由多个Mapper实现并行的映射，Reduce阶段由多个Reducer实现并行的规约，输出文件数量与Reducer的数量相同。基于MapReduce的地理数据水印算法流程如图1所示。

3.1 基于MapReduce的水印嵌入算法

水印嵌入算法主要有2部分组成。通过对数据集D进行数据分片后，交由Map阶段完成的主要任务是：完成每一地物的标识fid的计算，同时生成二进制字符串H，等待Reduce阶段进行水印嵌入使用。Mapper算法框架如下：

Procedure Embed.Mapper（ ）

Input：Dataset P={P1，P2，…，Pn}，Parameter h

Output：Binary Vector Set H（h1，h2，…hn ）

for all Pi in P do

Oi←comput_Central_Point（Pi ）//计算每一地物Pi的中心点Oi；

Pi.fid←msb（Oi，h）； // 生成地物Pi的标识

Pi.vNum←comput_Vertex_Num（Pi）//计算Pi的顶点数Pi.vNum

H←Hash（Pi_fid，Pi.vNum）//生成长度为Pi.vNum的二进制串

Emit（H）

水印嵌入算法Reduce阶段主要工作是：结合签名信息S，确定每一位水印的嵌入信息，生成二进制向量B，作为向外界发布的公开密钥。Reducer算算法框架如下：

Procedure Embed.Reducer（ ）

Input ： Pi={P1j，P2j，…，Pin}，SignatureVector S， BinaryVectorSet H Parameter t

Output：Binary Vector B={ b1，b2，…，bn }

for all Pij in Pi do

Pij.fid←msb（Pij，h）// 生成Pi中第J个顶点的标识

s=Hash（Pi.fid||Pij.fid） mod t//获取需要嵌入水印的位置

Bi [j]=Mid（Pij.fid，s，1）?H[j]?S[j]//Mid函数取Pij.fid的第s位，?代表异或算符

Emit（B）

3.2 基于MapReduce的水印检测算法

水印检测算法也有两部分组成。Map阶段完成的任务同水印嵌入阶段的Map阶段人物类似，不同的是针对的对象为待检测的数据集P，Mapper算法框架如下：

Procedure Extract.Mapper（ ）

Input ： Dataset P={P1，P2，…，Pn}，Parameter h

Output：Binary Vector H（h1，h2，…hn ）

for all Pi in P' do

Oi←comput_Central_Point（Pi ）//计算每一地物Pi的中心点Oi；

Pi.fid←msb（Oi，h）；// 生成地物Pi的标识

Pi.vNum←comput_Vertex_Num（Pi）//计算Pi的顶点数Pi.vNum

H←Hash（Pi_fid，Pi.vNum）//生成长度为Pi.vNum的二进制串

Emit（H）

水印检测算法Reduce阶段主要工作是：检测每一位水印的嵌入信息，生成二进制向量V，作为检测出的验证向量。算法框架如下：

Procedure Extract.Reducer（ ）

Input ： Pi={P1j，P2j，…，Pin}， Parameter t

Output：Binary Vector V={ v1，v2，…，vn }

for all Pik in Pi do

Pik.fid←msb（Pik，t）// 生成Pi中第k个顶点的标识

v=Hash（Pi.fid||Pik.fid） mod t//获取需要嵌入水印的位置

Vi [j]=Mid（Pik.fid，v，1）?H[j]//Mid函数取Pik.fid的第s位，?代表异或算符

Emit（V）

得到验证向量V之后，使用公开密钥B，调用ExtractSig（B，V）算法得到检测出的签名信息S'。其算法思想是将公开密钥B和检测出的验证向量C进行比较，对两个向量进行遍历，利用特征向量判别相应的地物是否被修改，得到检测出的签名信息S'。

完成上述工作之后，将检测出的签名信息S'，与代表数据所有权的签名信息S进行比较，如果一致即认为数据来源合法，否则不合法。

4 实验与结论

实验采用Intel CPU 2.4GHZ，内存8 GB，OS Win8.1宿主机，利用VMware WorkStation虚拟出3台相同的计算机。三台虚拟机分别安装Ubuntu12.04操作系统，1GB内存，并部署Hadoop 0.20.0构成集群，一台同时为Master和Slave节点，其他为Slave节点。开发环境为Eclipse Luna。实验数据为原算法的数据集，实验结果表明，本文算法可以处理大规模地理数据集。

参考文献

[1] Qingzhan Zhao，Lili Sui，Chuanjian Wang etc.Publicly Verify the Integrity of the Geographical Data Using Publlic Watermarking Scheme [C].GRMSE2013，Wuhan，2013，10.

[2] 汪传建，葛贺飞，丁卯等.一种基于可变步长量化调制的地理数据库水印方法[J].计算机研究与发展，2011，48（10）：1960-1971.

[3]彭熠玮，岳明亮，汪传建.基于MapReduce的高效地理数据水印方法[J].华中科技大学学报（自然科学版），2012， Vol 10，Sup 1：179-182.

作者单位

石河子大学信息科学与技术学院 新疆维吾尔自治区石河子市 832003