To　solve　the　possible　replay　attack　in　location　based　services　under　road　network,　two　algorithms　for　location　privacy　protection　based　on　equivalence　partitioning　were　proposed.　The　main　ideas　were　to　build　some　road　segment　cloaking　sets　which　meet　the　users＇　privacy　requirements　by　sequential　scanning　grouping　or　binary　grouping.　After　that,　all　road　segments　in　each　cloaking　set　were　anonymous　equivalence,　which　can　effectively　resist　replay　attack.　Experimental　analysis　was　designed　by　comparing　the　two　algorithms　in　this　paper　and　the　traditional　algorithms　on　service　respond　time　of　the　query　users.　Experimental　results　show　that　the　proposed　algorithms　in　this　paper　are　effective　and　feasible.