When　mobile　users　search　points　of　interest　in　location　based　services,　they　should　always　provide　their　accurate　locations,　which　may　leak　location　privacy　of　themselves.　A　typical　approach　to　protect　user　location　privacy　is　to　generate　a　cloaked　region　(CR)　that　encloses　the　user　position.　However,　if　locations　are　continuously　reported,　an　attacker　can　correlate　CRs　from　multiple　timestamps　to　accurately　pinpoint　the　user　position　within　a　CR.　In　this　paper,　we　present　a　novel　approach,　called　Extended　Guess-Answer,　to　protect　against　velocity-based　linkage　attacks　in　location　based　services.　Through　the　interaction　between　the　user　and　the　server,　a　cloaked　region　that　contains　user　current　location　can　be　generated.　The　experimental　results　show　that　our　approach　is　effective　and　feasible.　©　2012　IEEE.