一种路网环境中的轨迹隐私保护技术.PDFVIP

第３４卷第７期　　　 计算机应用与软件 Ｖｏｌ３４Ｎｏ．７ ２０１７年７月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ｊｕｌ．２０１７ 一种路网环境中的轨迹隐私保护技术 １ ２ 霍　峥 　王　腾 １（河北经贸大学信息技术学院　河北石家庄０５００６１） ２（中国电子科技集团第５４研究所卫星导航系统与装备技术国家重点实验室　河北石家庄０５００００） 摘　要　　不经过隐私处理直接发布轨迹数据会导致移动对象的个人隐私泄露，传统的轨迹隐私保护技术用聚 类的方法产生轨迹ｋ－匿名集，只适用在自由空间环境，并不适用于道路网络环境中。针对上述问题设计了一种 路网环境中的轨迹隐私保护方法，将路网环境中的轨迹模拟到无向图上，并将轨迹ｋ匿名问题归结到无向图的ｋ ｎｏｄｅ划分问题上。证明了图的ｋｎｏｄｅ划分是ＮＰ完全问题，并提出贪心算法解决此问题。通过实验验证了该算 法的匿名成功率平均接近６０％，最高可达８０％以上。 关键词　　路网　轨迹　隐私保护　数据发布 中图分类号　ＴＰ３　　　　文献标识码　Ａ　　　　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０１７．０７．０５７ ＡＴＲＡＪＥＣＴＯＲＹＰＲＩＶＡＣＹＰＲＯＴＥＣＴＩＯＮＴＥＣＨＮＯＬＯＧＹ ＩＮＲＯＡＤＮＥＴＷＯＲＫＥＮＶＩＲＯＮＭＥＮＴ １ ２ ＨｕｏＺｈｅｎｇ　ＷａｎｇＴｅｎｇ １（ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，ＨｅｂｅｉＵｎｉｖｅｒｓｉｔｙｏｆＥｃｏｎｏｍｉｃｓａｎｄＢｕｓｉｎｅｓｓ，Ｓｈｉｊｉａｚｈｕａｎｇ０５００６１，Ｈｅｂｅｉ，Ｃｈｉｎａ） ２（ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙｏｆＳａｔｅｌｌｉｔｅＮａｖｉｇａｔｉｏｎＳｙｓｔｅｍａｎｄＥｑｕｉｐｍｅｎｔＴｅｃｈｎｏｌｏｇｙ，Ｎｏ．５４Ｉｎｓｔｉｔｕｔｉｏｎ， ＣｈｉｎａＥｌｅｃｔｒｏｎｉｃｓＴｅｃｈｎｏｌｏｇｙＧｒｏｕｐＣｏｒｐｏｒａｔｉｏｎ，Ｓｈｉｊｉａｚｈｕａｎｇ０５００００，Ｈｅｂｅｉ，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ｄｉｒｅｃｔｌｙｐｕｂｌｉｓｈｉｎｇｔｒａｊｅｃｔｏｒｙｄａｔａｗｉｔｈｏｕｔｐｒｉｖａｃｙｐｒｏｃｅｓｓｉｎｇｃａｎｒｅｓｕｌｔｉｎｔｈｅｄｉｓｃｌｏｓｕｒｅｏｆｐｅｒｓｏｎａｌ ｐｒｉｖａｃｙｏｆｔｈｅｍｏｖｉｎｇｏｂｊｅｃｔ．Ｔｒａｄｉｔｉｏｎａｌｔｒａｊｅｃｔｏｒｙｐｒｉｖａｃｙｐｒｏｔｅｃｔｉｏｎｔｅｃｈｎｏｌｏｇｙｕｓｅｓｔｈｅｍｅｔｈｏｄｏｆｃｌｕｓｔｅｒｉｎｇｔｏｇｅｎｅｒａｔｅ ｔｒａｊｅｃｔｏｒｙｋａｎｏｎｙｍｏｕｓｓｅｔ，ｗｈｉｃｈｏｎｌｙａｐｐｌｉｅｓｔｏｆｒｅｅｓｐａｃｅｅｎｖｉｒｏｎｍｅｎｔａｎｄｄｏｅｓｎｏｔａｐｐｌｙｔｏｒｏａｄｎｅｔｗｏｒｋ ｅｎｖｉｒｏｎｍｅｎｔ．Ａｔｒａｊｅｃｔｏｒｙｐｒｉｖａｃｙｐｒｏｔｅｃｔｉｏｎｍｅｔｈｏｄｉｎｒｏａｄｎｅｔｗｏｒｋｅｎｖｉｒｏｎｍｅｎｔｗａｓｄｅｓｉｇｎｅｄｔｏｓｉｍｕｌａｔｅｔｈｅｔｒａｊｅｃｔｏｒｙ ｉｎｔｈｅｒｏａｄｎｅｔｗｏｒｋｅｎｖｉｒｏｎｍｅｎｔｔｏａｎｕｎｄｉｒｅｃｔｅｄｇｒａｐｈ，ａｎｄｔｈｅｋａｎｏｎｙｍｉｔｙｐｒｏｂｌｅｍｗａｓｒｅｄｕｃｅｄｔｏｔｈｅｋｎｏｄｅ ｐａｒｔｉｔｉｏｎｐｒｏｂｌｅｍｏｆｕｎｄｉｒｅｃｔｅｄｇｒａｐｈｓ．ＩｔｗａｓｐｒｏｖｅｄｔｈａｔｔｈｅｋｎｏｄｅｐａｒｔｉｔｉｏｎｏｆｔｈｅｇｒａｐｈｉｓａｎＮＰｃｏｍｐｌｅｔｅｐｒｏｂｌｅｍ ａｎｄａｇｒｅｅｄｙａｌｇｏｒｉｔｈｍｗａｓｐｒｏｐｏｓｅｄｔｏｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍ．Ｔｈｅａｎｏｎｙｍｏｕｓｓｕｃｃｅｓｓｒａｔｅｏｆｔｈｅａｌｇｏｒｉｔｈｍｗａｓｖｅｒｉｆｉｅｄｔｏ ｂｅｃｌｏｓｅｔｏ６０％ｏｎａｖｅｒａｇｅ，ａｎｄｔｈｅｍａｘｉｍ